题解

方向

先考虑根节点固定。

显然，代价为:

$$Ans = \sum _{(u,v)为轻边，且u为v的父节点} siz_{u} * ( n - siz_{u} )$$

设:

$$W = \sum _{u为v的父节点} siz_{u} * ( n - siz_{u} )$$ $$B = \sum _{(u,v)为重边，且u为v的父节点} siz_{u} * ( n - siz_{u} )$$

答案转化为:

$$Ans = W - B$$

由于 $W$ 是与根无关的常数（$siz_{u}*(n-siz_{u})$ 关于根对称），最小化 $Ans$ 等价于最大化 $B$。

最大化 $B$

树链剖分等价于每个结点独立地从儿子中选一个"重儿子"。因此:

$$B = \sum_{u} \max_{v\in sons(u)} siz_{v}*(n-siz_{v})$$

每个结点的选择互不影响，所以每个结点贪心取 $siz_{v}(n-siz_{v})$ 最大的儿子当重儿子即可。

注意:这里每条边的 $siz_{v}(n-siz_{v})$ 与根无关，故只需用任意根 DFS 一次求出每条边的固定权值 $w_{e}=siz_{v}(n-siz_{v})$。

换根

从根 $u$ 换到相邻点 $v$ 时，只有这两点的"候选儿子集合"改变：

• $v$ 由非根变根，候选集合多出边 $(u,v)$；
• $u$ 由根变非根，候选集合去掉边 $(u,v)$；
• 其余结点的父子方向不变。

所以只需把权值 $w$ 从 $u$ 的集合移到 $v$ 的集合，更新这两点对 $B$ 的贡献即可。用 multiset 维护每个结点候选儿子权值的最大值，单次增删、取最大值均为 $O(\log n)$。

复杂度

• 每次换根只移动一条边，进入/回溯各一次，$O(\log n)$。
• 每个结点作为根被处理一次，总复杂度 $O(n\log n)$，可过 $n\le 10^5$。
• 权值最大约 $2.5\times10^{14}$，需用 long long。

代码

数据结构

• g[u]：邻接表，存 $(相邻点, 该边固定权值w)$。
• cur[u]：multiset，存"以当前根为根时，$u$ 的所有儿子边权值"，用其最大值贡献到 $B$。
• sz, fa：任意根 DFS 求出的子树大小与父节点，用来给每条边定向并算 $w$。
• W, B, ans：总重边无关常数、当前根的重边贡献和、答案数组。

整体流程

1. 预处理：以 $1$ 为根 DFS，得到 fa 和 sz。对每条边算固定权值 $w=sz_{子}(n-sz_{子})$，累加得到 $W$。

2. 初始化根 $=1$：把每条边放入其"父节点"的 cur 中，即 cur[fa[i]].insert(w)。于是每个非根点的 cur 刚好是它以 $1$ 为根时的全部儿子边。累加每个点的 max(cur[u]) 得到 $B$，则 ans[1]=W-B。

3. 换根（核心）：写递归函数 rtt(u, from)，表示当前根为 $u$。对 $u$ 的每个邻居 $v\ne from$：

   • 把边权 $w$ 从 cur[u] 移到 `cur[v]$；
   • 用 max 前后差值更新 $B$（只有 $u,v$ 两点贡献变化）；
   • 记录 ans[v]=W-B；递归 rtt(v,u)；
   • 回溯时逆操作把 $w$ 移回，恢复 $B$。