树论?(啊对对对我没写错,不是数论,是树论)
树这东西……怎么说呢?
树是 OI 中一种常见于题面与算法中的玩意,兼具美丽与恶心的特性。树作为一张图的子集,它与图的关系紧密;而本身作为一种数据结构,又承担储存、组织数据的责任。
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ——老师
基本概念
树可以理解为一种数据结构,是由n(n≥1)个有限节点组成的一个具有层次关系的集合。
有根树一般存在有以下特点:
- 有一个节点被称作“根”。
- 这个根的所有孩子都是一棵子树的根。
与有根树相关联的概念:
- 父亲:对于除根以外的每个节点,定义为该节点到根路径上的第二个节点。根节点没有父节点。
- 祖先:一个节点到根节点的路径上,除了它本身外的节点。根节点的祖先集合为空。
- 子节点:如果u是v的父亲,那么v是u的子节点。
- 节点深度:到根节点的路径上的边数。
- 树的高度:所有节点的深度的最大值。
- 兄弟:同一个父亲的多个子节点互为兄弟。
除了有根树,还有“无根树”。
在处理与之相关的问题时,可以看作n个节点与n−1条边的无向图。
如果在无根树上指定一个节点为“根”,则满足了有根树的性质。
科普:
有根树在很多时候仍以无向图表示,只是规定了结点之间的上下级关系。
往往我们还有遇到一些带有特殊性质的树。例如二叉树、完全二叉树、慢二叉树、仙人掌等等,这些树的属性又赋予了他们处理不同问题的功能。
树上问题
DFS序
定义:对于一棵树来说,DFS 序即按照深度优先搜索的访问顺序,依次将访问到的点进行编号并记录。根据访问顺序取得的序列 即为 DFS 序。
深度优先搜索,即Depth First Search,简称DFS或深搜。
得出一棵树的 DFS 序后,对它的处理便可以向线性问题靠拢。这是一个很重要的思想。将复杂的结构通过一定的方式简化,使其变得线性,更加容易处理。
BFS序
定义:对于一棵树来说,BFS 序即按照广度优先搜索的访问顺序,依次将访问到的点进行编号并记录。根据访问顺序取得的序列 即为 BFS 序。
广度优先搜索:又称宽度优先搜索,即Breadth First Search,简称BFS、广搜或宽搜。
DFS BFS总结:
- dfs序中一个结点的子树结点一定是连续的。
- bfs,dfs序中的一个结点u的后续结点一定是u或u的后兄弟结点{v},或u和{v}的后代节点{s}。
- 如果有后兄弟结点,那么bfs序中u后面紧跟着的一定是第一后兄弟结点v1,
- 如果有后代结点,那么dfs序中u后面紧跟着的一定是第一个子结点s1。
前序、中序、后序排列
定义:
- 前序遍历
- 先输出父结点,再左结点,最后右结点(父左右)
- 中序遍历
- 先输出左结点,再父结点,最后右结点(左父右)
- 后序遍历
- 先左结点,再右结点,最后父结点(左右父)
例如:
前序:ABDGHICEJF
中序:GDIHBAEJCF
后序:GIHDBJEFCA
树的直径
定义:树上任意两节点之间存在的最长简单路径,就被称作树的直径。
可以用两次DFS、两次BFS或者树形DP进行求解。
最近公共祖先(Lowest Common Ancestor)
定义:最近公共祖先,简称LCA,也就是两个节点的公共祖先中,距离“根节点”最远的那一个节点。
可以用向上标记法、树上倍增法、Tarjan算法、树链剖分、欧拉序+st表等算法进行求解。
树的重心
定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
这里以及下文中的“子树”都是指无根树的子树,即包括“向上”的那棵子树,并且不包括整棵树自身。
一些性质:
- 以树的重心为根,所有子树的大小都不超过整棵树大小的一半。
- 树中所有点到某个点的距离和中,到重心的距离和是最小的。如果有两个重心,那么到它们的距离和一样。
- 把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两棵树的重心的路径上。
- 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。
求法:见AcWing 846. 树的重心
最小生成树
生成树定义:一个连通图的生成子图,同时要求是树。即在图的边集中选择n−1条边,将所有顶点连通。
最小生成树定义:即权值和最小的生成树。
只有连通图才有生成树,而对于非连通图,只存在生成森林。
主要求解方法:Prim、Kruskal、Boruvka。
- Kruskal 算法的基本思想是从小到大加入边,核心是贪心算法。
- Prim 算法是另一种常见并且好写的最小生成树算法。基本思想是从一个点出发,不断加点。
- Boruvka 的思想则可以看作二者的结合。
树链剖分
因为太长了所以我把树链剖分单独放了一个帖子
“因为太长了所以我把树链剖分单独放了一个帖子”
其实你只是想赚阅读量对吧。。。你觉得是,我就算再怎么说不是你也觉得是,我说的再怎么秀,辩论的再怎么好,你还是觉得我在骗阅读量。。。
难道你不觉得我那个树链剖分的帖子雀食有点长吗……放在这里感觉一大堆公式挤在一起
我不想让AcWing再炸一次
但是acw有很多分享都是很长的呀QwQ你是说我的 A+B 是用来炸 AcWing 的吗考咕awa
烤谷考古Conan15 与 2AK 游于 AcWing 之中,2AK 曰:“Conan15 开两个帖,是想赚阅读量也。”Conan15 曰:“子非 Conan15,安之 Conan15 之赚阅读量?”2AK 曰:“子非我,安知我不知 Conan15 之赚阅读量?”Conan15 曰:(重头戏)“吾乃 Conan15 是也!”2AK 曰:“
¥&*)@#%*()@#¥%!)@#¥(¥&%!@#¥
”dalao 您会
向上标记法、树上倍增法、Tarjan算法、树链剖分、欧拉序+st表
这么多方法,我只会一种。。。太强拉!!!
封禁用户yyds!
可恶
我只是知道有这些办法有待学习,你没看到我没写这些算法怎么做的吗……
我只会向上标记法。。。
tql,那天那啥你居然都听懂了
(我树链剖分都在划水)
aaa,其实那天下午我不在……
我去医院了,树链剖分我一直想学刚好没听到QwQ
树链剖分听说挺简单的,我去学一下
《挺简单》
大神们都是这么说的,我早被吊打了
az
我不会,您吊打我
——老师tql
封禁用户 邹成功说和你势不两立!
我不支持邹成功
邹成功 太菜了
树链剖分我都不会
额额额我的评论呢
你好像忘了几点,先序遍历,中序遍历…(不打了,你知道)
好的
今天太晚了,明天有时间再更QwQ
慢着你确定8:20算晚
还有老师编程作业
呃…好像熬个夜就可以完成了已加入
还有个bfs序
就是bfs遍历顺序吧,我去加入一下
欧克,而且我上网搜了一下dfs bfs序的性质
dfs序主要应用是和线段树,树状数组结合
好的谢谢
cai
?
我就知道我很菜,大佬直言吧
azzzzzzzzzz
真.菜
邹成功菜得像个 xiao ji er 一样