树链剖分（decomposition）

定义一个树的一种树链剖分的权值为：所有 $(u,v)(u\le v)$ 之间的经过轻边的个数的和。

定义一个树的最优树链剖分为权值最小的树链剖分。

给定 $n$ 个点的树。

对于每一个节点 $i$，求以 $i$ 为根的情况下的最优树链剖分的权值。

$n\le 10^5$。

显然的换根 DP，于是我们先考虑单次树形 DP 怎么求。

首先我们应该拆贡献：对于每一条边 $(u,v)$，其中 $u$ 是 $v$ 的父亲，那么共有 $sz_v(n-sz_v)$ 个路径经过它。那么只要其不是重边，答案就要累加这个值。

于是我们定义 $f_x$ 表示考虑 $x$ 子树内的所有边的贡献的最小权值，则有：

$$f_x=\sum_u f_u+\sum_u sz_u(n-sz_u)-\max_u\{sz_u(n-sz_u\}$$

设 $d_{1,x},d_{2,x}$ 表示 $x$ 子树内最大次大的 $sz_u(n-sz_u)$。同时定义 $D_{1,x},D_{2,x}$ 为达到 $d_{1,x},d_{2,x}$ 的儿子。

直接模拟可以做到 $\mathcal{O}(n^2)$。

然后就是换根 DP（多画图，不然很可能看不懂下面的）。

不妨设 $g_x$ 表示以 $x$ 为根时的 DP 值，且我们现在要从 $g_x$ 转移到 $g_u$。

那么 $g_u$ 应该分为 $5$ 个部分：

1. $f_u+d_{1,u}$，因为 $d_{1,u}$ 可以变化，通过 $u\to x$ 这条边进行更新。
2. $-\max\{d_{1,u},sz_u(n-sz_u)\}$，这里就是利用 $u\to x$ 这条边更新。注意，这次的通过父节点的更新应该永久的带到 $u$ 的子树中，因为以 $u$ 子树为根时依然有 $u\to x$ 这条边。
3. $sz_u(n-sz_u)$，因为要加上 $u\to x$ 这条边的贡献。
4. $g_x-f_u-sz_u(n-sz_u)+d_{1,x}$：要加上 $u\to x$ 的贡献。同时 $g_x$ 需要去掉 $u$ 这一部分。并且，由于去掉了 $u$ 子树，$d_{1,x}$ 可能更新。
5. $-\begin{cases}d_{1,x}& D_{1,x}\ne u\\d_{2,x}&D_{1,x}=u\end{cases}$。

然后模拟即可 $\mathcal{O}(n)$。

题解

方向

先考虑根节点固定。

显然，代价为:

$$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$。