树链剖分（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)$。