二维数点.
考虑每个点 $x$ 会在删掉哪些边后成为重心,把它的贡献加到那些边上去.
考虑 $x$ 的所有子树(包括父亲方向的),分删掉的边是否在最大子树中进行讨论.
$x$ 要成为新的重心,最大子树大小不能超过全局的一半,可以简单得出断掉的部分节点数应当在某个区间 $[l,r]$ 中.
若断掉的边是在 $x$ 某个儿子的子树内,那么断掉的节点数就是那条边下方的子树大小.
这等价于对于 dfs 序在某个区间内,且下方子树大小在某个区间的边的答案加上了 $x$ ,是个二维数点问题.
若断掉的边是在 $x$ 父亲方向的子树上,当它不在 $x$ 到根的路径上时,断掉的节点数也是下方子树大小.
当它在 $x$ 到根的路径上时,断掉的节点数是 $n$ 减去下方子树大小.
可以先把断掉的节点数都当成是下方子树大小,再对每条边考虑子树中的每次操作,将对应的贡献修改过来.
用主席树维护这个二维数点即可,时间复杂度 $O(n\log n)$ .