P7238「DCOI」迷失森林 题解
JackMerryYoung
·
·
题解
前言
第一眼看这道题时，还以为是 DFS。（太蒻了）
结果看了标签，树形 DP 好题。
看到这里，有些人又会说，树形 DP 是啥，咋写？
如果对树形 DP 不太熟悉的同学，可以先去洛谷做一些题目，下面推荐一些经典的好题：
经典好题，这里不再赘述了，想学的先 AC 这道题。
极其良心变态的一道题目，在这里表扬出题人。
名字长得像拓扑排序，但是个 DP。
- P7846 「dWoi R2」Arcade hall / 街机厅
这道题一看就知道是树的直径问题，只不过树变成了森林。
解法
有些人可能不知道树的直径问题，树的直径指的是树中的最远的两点间距离。
一看这个题面，可能有人认为这个题很难，什么“单位树”啊、“简单路径”啊、看起来对一些刚学图论的萌新很不友好。
但是，这题并没有很难。
设 \Large{f_i} 为以第 i 棵单位树的的第 1 个节点，也就是题目描述中的二元组 (i, 1)，为连接操作的链的一端所获得的最大直径。
显而易见，\Large{f_i} 的值从两个来源贡献而来。
第一个是单位树的最大直径，即为代码中的 maxdepth，这个很容易预处理得来。（见我代码中的深搜）
第二个是单位树的儿子，这里叫 son，还有自己到根节点的深度 depth_i。
$$
f_i = \max\{maxdepth, f_{son} + depth_i\}
$$
这里再给出树形 DP 的一般形态。
``` cpp
void dfs(int u, int fa)
{
f[u] = __start_value;
for(int i = head[u]; i; i = edge[i].nxt)
{
int v = edge[i].to;
if(fa == v) //判重
continue;
dfs(v, u); //下一层
f[u] = max(f[u], f[v] + w);
}
}
```
言归正传，这题到这里还没有结束，$f_i$ 并不是我们要的答案。
这个时候维护两个值，最大子树直径与次大子树直径，即为代码中的 $max1$ 与 $max2$。
将这两个值相加并加上 $1$（因为要算上自己），取最值即可。
方程如下：
$$ans = \max\{max1 + max2 + 1\}$$
至于放在哪里，在 DP 的时候顺带维护一下即可。
至此，这道题到现在总算完结了，是不是难度还好呢？
# 代码
~~你们最想要的..~~
Talk is$\color{white}\text{n't}$ cheap, $\color{white}\text{Don't}$ show me the code...
没写链式前向星，看题解区大佬们都没写，也就没写...
``` cpp
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> edge[1000005];
long long f[1000005], ans;
int depth[1000005];
int maxdepth;
void get_depth(int u, int v);
void dfs(int u, int v);
int main()
{
cin >> N;
for(int i = 1; i < N; i ++)
{
int x, y;
cin >> x >> y;
edge[y].push_back(x);
edge[x].push_back(y);
}
get_depth(1, 1);
dfs(1, 1);
ans = max(ans, f[1] + maxdepth - 1);
cout << ans << endl;
return 0;
}
void get_depth(int u, int v)
{
depth[v] = depth[u] + 1;
maxdepth = max(maxdepth, depth[v]);
for(int i = 0; i < edge[v].size(); i ++)
{
int to = edge[v][i];
if(u == to) //判重
continue;
get_depth(v, to);
}
}
void dfs(int u, int v)
{
f[v] = maxdepth;
long long max1 = -1, max2 = -1;
for(int i = 0; i < edge[v].size(); i ++)
{
int to = edge[v][i];
if(u == to) //判重
continue;
dfs(v, to);
if(f[to] > max1)
{
max2 = max1;
max1 = f[to];
}
else if(f[to] > max2)
{
max2 = f[to];
}
f[v] = max(f[v], f[to] + depth[v]);
}
ans = max(ans, max1 + max2 + 1);
}
```
# 后言
阅读完这篇题解，你可能对于树状 DP 有了初步的了解，后面的 DP 将会越来越复杂，不仅复杂在状态的转移，更在优化的繁琐。
在这里，本人衷心祝愿每一位学习 OI 的人都不要因为一时的困难而放弃，越来越强！