题解

思路

设最终把根移到顶点 $v$。移动根的最少次数就是初始根 $1$ 到 $v$ 的边数 $d_1(v)$。若 $e(v)$ 表示 $v$ 到最远顶点的边数，则收益为

问题转化为求所有顶点中该式的最大值。

做法

小规模时，可以依次把每个顶点当作根，遍历整棵树求其偏心距 $e(v)$，总复杂度为 $O(n^2)$。

若 $c\ge k$，从顶点 $1$ 移动 $d$ 条边后，偏心距至多比 $e(1)$ 增加 $d$。因此新收益至多为

不移动一定最优，只需求一次从 1 出发的最远距离。

一般情况下使用树直径。任取顶点 $s$，找到离它最远的顶点 $A$；再从 $A$ 出发找到最远的顶点 $B$，则 $A,B$ 是一对直径端点。树上任意顶点 $v$ 的最远顶点一定可以取为某个直径端点，因而

分别从 $1,A,B$ 遍历树得到三组边数距离，再枚举 $v$ 代入收益公式即可。

正确性证明

移动根只改变根的位置，不改变树。树上从 1 到 $v$ 的路径唯一，因此到达 $v$ 的最少移动费用恰为 $c\cdot d_1(v)$；售价则恰为 $k\cdot e(v)$，收益公式成立。

树直径端点性质保证对每个 $v$，到全树最远点的距离等于它到 $A,B$ 两者距离的较大值。三次遍历得到的 $d_1,d_A,d_B$ 均为树上的精确距离，所以算法为每个可能的新根计算了精确收益。枚举所有顶点取最大值，所得结果就是全局最优收益。

复杂度分析

每个测试用例进行常数次树遍历，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。所有测试用例总复杂度为 $O(\sum n)$。