一般求解跟路径有关的问题。

边分治

中心边：当前树断开这条边，将树分成的两部分大小最大值最小。

类比点分治，我们考虑找到一条中心边 \((u,v)\) ，考虑强制钦定经过该边和不经过该边分别求解。

发现菊花图卡 T，三度化后就正确了。

边分树

其实正确的应该叫做边分树合并。

一开始是一个由链组成的森林，链从根到底分别是从边分治开始到结束的所属的连通块的编号。

如何构造链：对于一个边分治过程，若当前中心边为 \((u,v)\)，那么就在 \(subtree(u)\) 中每一个节点的链底左儿子加一个点 \(v\)，在 \(subtree(v)\) 中每一个节点的链底左儿子加一个点 \(u\)。

计算答案原理：点对 \((u,v)\) 对答案产生贡献一定是第一次不属于同一个连通块。过程类似线段树合并。

真简单。