自动搬运

查看原文

来自洛谷，原作者为

	言琢დ “我会成为这里的主宰，清除掉整片土地上的一切障碍，只留下我跟那一堆白骨，她永远不朽，而我不死不灭。”

搬运于2025-08-24 22:27:58，当前版本为作者最后更新于2021-04-09 10:03:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$$\large\text{「DCOI」迷失森林}$$ $$\text{Znloye}$$ $$\text{2021 年 4 月 9 日}$$

$1~\text{树的直径}$

Subtask5 满足 $n\le10^3$，因此可以 $O(n^2)$ 模拟建树。

以 $u$ 为根的子树中，$u$ 必选时树的直径为 $d_1+d_2-1$。

其中 $d_1,d_2$ 分别表示以 $u$ 为根最大、次大深度。

$2~\text{森林直径}$

引理：森林直径必由树的直径扩展而来。

证明：一条边 $(u,v)$ 若存在于树的直径中，必在森林中有一对应子树存在。

此时该对应子树对应的最长链一定是森林的最长链。

设 $d_1[u],d_2[u]$ 分别表示以 $u$ 为根最大、次大深度，$d[u]$ 表示以 $1$ 为根 $u$ 的深度，$v$ 是 $u$ 的孩子。

考虑到以 $u$ 为根子树的转移：

$$\begin{aligned}&d[v]=d[u]+1\\&d_2[u]\leftarrow d_1[u],d_1[u]\leftarrow d_1[v]+1~~~(d_1[u]<d_1[v]+1)\\&d_2[u]\leftarrow d_1[v]+1~~~(d_2[u]< d_1[v]+1\le d_1[u])\end{aligned} $$

记 $S(n)=\frac{n(n+1)}{2}$，以 $u$ 为根，森林直径必过 $u$ 的答案：

$$Ans_u\leftarrow S(d_1[u])+S(d_2[u])+d[u]\times(d_1[u]+d_2[u]-2) $$

最终森林直径：

$$Ans=\max_{u\in T}\{Ans_u\}+d_1[1]\times2+1$$

$\rm code\Leftarrow$