P10794 『SpOI - R1』架子鼓可以站 C 题解

zrl123456 · 2025-10-21 11:55:49 · 题解

:::::info[题目基本信息] 考察：树形 DP，动态规划 DP（省选/NOI-）。
题目简介：

• 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