如下。目测 TLE + MLE ，怎么优化？

听兔说可以用树上差分+BIT 来维护线段树合并维护的那些东西，然而我不会/kk

对于一个结点 x，统计它会在多少次断边后变成重心。

记以 x 为根时，v 大小为 $siz[x][v]$，重儿子为 $son[x][v]$，次重儿子为 $son2[x][v]$，父亲为 $fa[x][v]$。

注：实际上不开二维数组，因为事实上计算 x 的时候只需要用到以 1 为根和以 x 为根的信息。前者预处理，后者用 LCT 来每次换根就行。

1. 在以 $fa[1][x]$ 为根的子树里割掉一条边，这条边为 $fa[x][del]->del$。即割掉以 del 为根的子树。则应当满足：

   $siz[1][son[1][x]]\le\dfrac{n-siz[x][del]}2;n-siz[1][x]-siz[x][del]\le\dfrac{n-siz[x][del]}2$，即：

   $n-2siz[1][x]\le siz[x][del]\le n-2siz[1][son[1][x]]$。

   需要维护的东西有：$fa,siz,son,son2$，以及以 x 为根的时候 x 各个子树中 $siz$ 为 i 的个数。

   这个个数可以用线段树合并来维护。可以用一个 Link Cut Tree 来维护这些东西（因为要换根）。

   但这么做会导致重复，即重复计算了以 $fa[1][x]$ 为根的子树中的信息。

   再开一组线段树合并来计算即可。

2. 在以 x 为根的子树中割掉一条边，这条边为 $fa[x][del]->del$。即割掉以 del 为根的子树。再分两种情况讨论：

   2.1 del 不在以 $son[1][x]$ 为根的子树里面。

   则应当满足 $2siz[1][son[1][x]]\le n-siz[1][del];2n-2siz[1][x]\le n-siz[1][del]$。这个用线段树合并随便维护即可。

   2.2 del 在以 $son[1][x]$ 为根的子树里面。

   则应当满足 $2siz[1][son2[1][x]]\le n-siz[1][del];2n-2siz[1][x]\le n-siz[1][del]$。也可以用线段树合并来维护。

$\huge 实现难度=\dfrac k{思维难度}$