非常好题目，结论差点就真了。
手玩几棵树的构造过程，会发现我们每次都是先从一个点开始，点亮其子树所有点，然后到父亲，点亮父亲子树所有点，如此往复直到某个拐点
，又往下走到某个点 ，熄灭在 子树但不在
子树的所有点，如此往复，到达某个点时停下。
那么，这个过程相当于在树上走出一条链，那么在这条链上的点的限制都能得到满足，但代价是
链上深度最浅的点的子树大小。
设链的端点为 ，需要注意的是，链并不一定是形如 的，可能会在到达
后，又往上走一段，又折返下来，即找到某个 的祖先 ，走出形如 的路径。此时代价为 。
那么原问题转化为，找到若干条这样的路径，使得树上每个点被覆盖至少一次，最小化代价和。
因为 并不一定是 ，所以我们难以知道以
为端点的链会在哪里合并起来。不如直接对链上的每条边计算代价，而不是关注
具体是多少。具体地，对于 和 的边，代价都是 。对于一条链的端点，代价就是 。一条链就由两个部分组成：边被经过
次和 次的部分。
所以设 表示 子树内还有
条链的端点没有找到与其对应的端点（即这些链还处在”边被经过一次“的阶段）， 有没有被至少一条链经过则用 表示。
的初值就是 。
在合并 的 DP 数组和儿子 的 DP 数组时，分讨 边被经过 次（经过 次的情况可以调整到不超过 次）。那么有转移：
上述三类分别代表 经过
次的转移。
于是本题就做完了，时间复杂度 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <bits/stdc++.h>
using namespace std;
template<typename T> inline void ckmin(T &x,const T &y) { if(x > y) x = y;}
const int N = 2e5 + 5;
int n;
vector<int> G[N];
int dp[N][2][2],sze[N];
void dfs(int x,int fa) {
sze[x] = 1;
for(auto y : G[x]) if(y != fa) dfs(y,x),sze[x] += sze[y];
int tmp[2][2];memset(tmp,0x3f,sizeof tmp);
dp[x][0][0] = 0;dp[x][1][1] = sze[x];dp[x][0][1] = sze[x] + sze[x];
dp[x][1][0] = 0x3f3f3f3f;
for(auto y : G[x]) {
if(y == fa) continue;
for(int i = 0;i < 2;i++)
for(int j = 0;j < 2;j++) {
ckmin(tmp[i][j],dp[x][i][j] + dp[y][0][1]);
for(int k = 0;k < 2;k++)
ckmin(tmp[i ^ 1][j | k],dp[x][i][j] + dp[y][1][k] + (sze[x] - sze[y])),
ckmin(tmp[i][j | k],dp[x][i][j] + dp[y][0][k] + 2 * (sze[x] - sze[y]));
}
for(int i = 0;i < 2;i++)
for(int j = 0;j < 2;j++)
dp[x][i][j] = tmp[i][j],tmp[i][j] = 0x3f3f3f3f;
}
}
int main() {
cin >> n;
for(int i = 2,x;i <= n;i++) cin >> x,G[x].push_back(i);
dfs(1,0);
cout << dp[1][0][1] << endl;
return 0;
}
|