树的基础知识

树的直径

就是树上最长的路径
最简单的方法就是两次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 序连续