边分治就是，每次选择一条边作为分治中心。然后把这条边断掉，在两个连通块内继续递归。
考虑将原树三度化，就是对于 \(u\) 的每条出边，新建一个点 \(w\)，连边 \((u, w, 0), (w, v, d)\)，然后令 \(u = w\)。三度化后边分治的复杂度就是对的，为 \(O(n \log n)\)。
边分治的好处是，每次只用考虑两个连通块的贡献。
进行边分治时，每个点有一棵二叉树和指向这个二叉树的某个结点，称这个为 \(a_u\)。初始时每棵二叉树都只有一个结点，\(a_u\) 就是唯一的那个结点。
然后每次分治，称在一个连通块内的点为黑点，另一个连通块内的点为白点，若当前点为黑点那么给 \(a_u\) 新建一个左儿子并且移动 \(a_u\) 到新建的这个点，否则新建右儿子。
这样边分治结束后每个点都维护了一棵独一无二的二叉链。有什么用呢？
如果两个点的二叉链在某个点上面都相同，那么表示这两个点在这些分治过程中都被分到了同一边。在某个点分叉说明从某个分治过程开始两个点不在同一个连通块了，两点间路径信息应该在这个点被统计。
每个点的边分树是可以合并的，复杂度和线段树合并相同。所以我们可以在合并时统计一些信息。
1. P4565 [CTSC2018] 暴力写挂
考虑把其中一个 \(\text{dep}(\text{lca}(x, y))\) 去掉。答案的式子可以化成：
\[\frac{\text{dis}(x, y) + \text{dep}(x) + \text{dep}(y) - 2 \text{dep}'(\text{lca}'(x, y))}{2} \]考虑建出边分树，然后在第二棵树上 dfs，在 \(\text{lca}\) 处边分树合并统计不同子树的信息。
边分树上每个点维护一个 \(g_u\) 表示子树内 \(\text{dis}(x, u) + \text{dep}(x)\) 的最大值。合并时，有 \(ans \gets \max(g_{ls_u} + g_{rs_v} - 2d, g_{ls_v} + g_{rs_u} - 2d)\)。然后更新 \(g_u \gets \max(g_u, g_v)\)。
时空复杂度均为 \(O(n \log n)\)。
标签：分树,连通,dep,text,分治,二叉树 From： https://www.cnblogs.com/zltzlt-blog/p/17988230