转载：

大致题意： 给你一棵树，询问对于每个点需要改变多少条边来使得它成为树中到所有点距离和最小的点。

一些初始化及想法

首先我们要知道一个结论：对于这棵树的重心，它的答案必定为0。

然后对于非重心的点该怎么办呢？

我们考虑把重心作为根，并统计出每个子节点的Size。

接下来我们可以发现，如果割掉根节点的若干棵子树，且这些子树 Size之和 ≥ n/2，那么肯定就可以构造出一种合法的方案使得任意节点符合条件。

由于要割的次数最少，因此我们将根节点的子节点按Size从大到小排序，然后取尽量少的节点使得Size和≥n/2，并记录所需节点数为p。

答案的取值

对于除重心外的每个点，其答案只可能为p或者p−1。

什么时候能够取p−1呢？

假设一个点x位于根节点的子节点排序后的第i个子节点的子树内。

对于i≤p，我们割去除i外第1∼p个点到根节点的连边。如果这些被割去的子树的Size和加上Size_x ≥ n/2，那么我们就不需要再割一条新边了。

而对于i>p的情况也是类似的，只不过一开始割去的是第1∼p−1个点到根节点的连边。

按照这样的方式，我们就可以求出答案了。