Link
题解
首先需要学习边分治。
边分治和点分治都属于树分治，但点分治是找重心，边分治是找“重心边”（即两端子树 \(\text{size}\) 最大值最小的边）。
然而直接找重心边复杂度是错误的，hack 的话一颗菊花就足够了。
所以我们要对原树进行三度化操作，这通常也是最难的部分之一。
一种常用的方法是建虚点链，即如图所示：
其中 \(1\) 系列的点全部是虚点，\(1\) 系列的点之间的连边全是虚边，设置虚点和虚边所扮演的角色是边分治的一大难点。
容易发现，这样的树每个点度数至多为 \(3\)，复杂度正确。
一般来讲，点分治能干的事情边分治大多都能干。
标签：jijfwros,重心,复杂度,分治,虚点,虚边 From： https://www.cnblogs.com/CCPSDCGK/p/17114852.html