「DCOI」迷失森林
言琢დ
·
·
题解
\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