本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-21 11:55:49

:::::info[题目基本信息] 考察：树形 DP，动态规划 DP（省选/NOI-）。
题目简介：
$t$ 组数据，每组数据给你一棵有 $n$ 个点的有根树，根为 $1$，你可以进行若干次操作，每次操作为：

• 选择一个叶子结点 $x$，删除一条 $x$ 到 $1$ 的路径上的一条边，并增加一条 $x$ 到 $1$ 的边。

求进行若干次操作后树的直径的最大值。
数据范围：

• $1\le t\le 10^4$
• $1\le n\le 2\times 10^5$
• $\sum n\le 3\times 10^6$

时间限制：2s。
空间限制：512MB。
::::: 容易发现几个性质：

1. 最后的树的所有直径一定过 $1$。 :::::success[证明] 如果存在一条直径不过 $1$，那么将这棵子树的根节点和它的父亲断掉并连接 $1$ 和直径的一个端点（即一次操作）会使直径变长。
   :::::
2. 若在直径最长的基础上让操作数最小，那么最后的直径一定过所有新增的边。 :::::success[证明] 容易发现，如果最后直径不过这条边，那么这次操作就浪费了。
   :::::
3. 在 2 的条件下，操作数上界为 $2$。 :::::success[证明] 结合 1 和 2 容易得到。
   :::::

既然操作数上界为 $2$，那么我们分类讨论：

1. 操作数为 $0$，答案为原树直径。
2. 操作数为 $1$，答案为某个子树的直径拼上一条其它子树的叶子到根根的链。
3. 操作数为 $2$；两条不交的链拼起来。

容易发现操作树为 $0$ 和 $1$ 的情况都是 $2$ 的特例，那么我们进行 $2$ 次操作一定不劣。
现在问题转化为如何求树上两条不交的链的长度和最大值。
不妨枚举子树，分别求出子树内的直径和子树外的直径，拼起来就是答案。
子树内的直径求法是平凡的，问题在于如何求出子树外的直径。
对于两条直径不在 $1$ 的同一儿子的情况，我们直接枚举子树，简单转移即可。
对于位于同一儿子子树内的情况，考虑树形 DP，设 $dp_u$ 为 $u$ 所处的 $1$ 儿子子树内 $u$ 子树以外的最长直径，当从 $u$ 转移到儿子 $v$ 时，需要转移父亲和所有兄弟的贡献。

1. 父亲：令 $dp_v\leftarrow\max(dp_v,dp_u)$。
2. 兄弟之内：令 $\displaystyle dp_v\leftarrow\max(dp_v,\max_{w\in\text{son}_u,v\ne w}f_w)$，其中 $f_w$ 表示 $w$ 子树内的直径，这个东西可以预处理前后缀最值实现。
3. 兄弟之间：记录所有 $u$ 的所有不同儿子的前三长链，之后容易计算。

这样累计答案就做完了。
:::::warning[坑点] 别忘了 $n=2$ 的 corner case。
::::: 时空复杂度均为 $\Theta(n)$。

code