树的基础知识

73

树的基础知识

树的直径

就是树上最长的路径
最简单的方法就是两次dfs,一次找端点,另一次找另一端点
或者也可以用树形dp,开一个数组 dp 记录节点向下的最长路径长度,然后在每次更新前更新最终答案 d 的值,再更新 dp 的值(因为最大值之前 dp 肯定是次大值)

性质: 若树上所有边边权均为正,则树的所有直径中点重合

树的重心

dfs,最大子树 size \leq n/2

性质:

  • 树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么到它们的距离和一样。
  • 把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两棵树的重心的路径上。
  • 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。

最近公共祖先

dfs 序法

抛弃欧拉序,让欧拉序成为时代的眼泪 —— Alex Wei

先跑一遍 dfs,记录节点对应 dfs 序和 dfs 序对应节点以及节点深度
对求查询的两个端点dfs序之间深度最小的节点,若这个节点为端点,则这个节点就是它们的最近公共祖先,若不是,最近公共祖先即为该节点的父亲

tarjan

利用回溯的思想,加上并查集,如果遍历完某个节点之后询问的另一个子节点已经被访问,则另一个节点的父亲就是 lca。
具体细节:先初始化并查集,将询问用邻接表存储,开一个 visited 数组,在遍历完某一结点后,将自己的父亲从自己设为自己真正的父亲(大雾),然后遍历询问的另一边,如果访问过了,则将两条边的 lca 都设置掉。

树链剖分

两次 dfs,一次记录大小,父亲,深度和重儿子,一次写入链顶,记录 dfs 序
细节:第一次用深度判断父亲,第二次优先处理重儿子保证同一条链 dfs 序连续