题解 P7238 【迷失森林】
Hexarhy
2021-01-02 16:35:13
## Preface
这里是官方题解。
**考察：树形 dp 、树的直径。** 适合普及组选手练习基础。
其实这题的是想加强到 $k$ 阶（把上一阶的“大树”作为新的单位树重复操作），但最后还是这样。
部分分做法请私信出题人@诡辩巫师。
## Solution
比较套路的树形 dp。
设 $f_i$ 表示在 $(i,1)$ 的子树中，以 $(i,1)$ 为**端点**的最长链长度。
定义 $dep_{\max}$ 为一棵单位树中深度最大的点的深度，$dep_i$ 为一棵单位树中节点 $i$ 的深度，$s_i$ 为单位树上 $i$ 的**直接儿子**。这些都可以在一棵单位树一次 dfs 得到。
考虑 $f_i$ 的贡献从哪里来。简单地观察可以得出贡献来源：
- $(i,1)$ 所代表的一棵单位树，贡献为 $dep_{\max}$。
- $s_i$ 所代表的单位树，贡献为 $f_{s_i}+dep_i$。
那么转移为：
$$
f_i=\max\{f_{s_i}+dep_i\}
$$
至于边界值，就是叶节点的值，显然就是该叶节点所代表的单位树的 $dep_{\max}$。
但是 $f_i$ 并不是题目要求的答案。对于节点 $(i,1)$ 所在子树：
- 其直径为最大的两个 $f_{s_i}$ 拼起来，即 $\max\{f_{s_i}\}+\max'\{f_{s_i}\}+1$。$\max'$ 表示次大值。$+1$ 是节点 $(i,i)$。
那么在从下往上维护 $f_i$ 的同时，顺便更新答案 $\rm ans$。
最后还要特判一下，可能编号 $1$ 节点的最大值不是两个 $f_{s_i}$ 拼起来的，而是一个最大的 $f_{s_i}$ 和自己所代表的单位树深度的贡献（比如没有次大值），因此要把答案再与 $f_1+dep_{\max}-1$ 取最大值。$-1$ 是因为根节点算了两遍。
上述过程都可以在一棵单位树中完成，时间复杂度 $O(n)$。
## Code
**本代码需要 C++11。**
```cpp
void dfs1(cint& u,cint& Fa)
{
fa[u]=Fa;
dep[u]=dep[Fa]+1;
for(const auto& v:edge[u])
{
if(v==Fa) continue;
dfs1(v,u);
}
}
void dfs2(cint& u)
{
if(edge[u].size()==1 && u!=1)//叶节点
{
f[u]=maxdep;
return;
}
ll max1=0,max2=0;//最大值和次大值
for(const auto& v:edge[u])
{
if(v==fa[u]) continue;
dfs2(v);
if(f[v]>max1) max2=max1,max1=f[v];
else if(f[v]>max2) max2=f[v];
f[u]=max(f[u],f[v]+dep[u]);
}
ans=max(ans,max1+max2+1);
}
int main()
{
read(n);
for(register int i=1;i<n;i++)
{
int u,v;read(u,v);
edge[u].emplace_back(v);
edge[v].emplace_back(u);
}
dfs1(1,1);
maxdep=*max_element(dep+1,dep+1+n);
dfs2(1);
cout<<max(ans,f[1]+maxdep-1)<<endl;//最后特判
return 0;
}
```