题意：树的最小点覆盖，选择最少的点覆盖所有边。
分析：
- 状态：f[u][0/1] 表示不选/选编号u的点的最优解
- 转移：
不选u，则一定选u的儿子v，即 f[u][0] +=f[v][1]
选u，则可以选，也可以不选u的儿子v，即 f[u][1] += min(f[v][0], f[v][1]); - 目标：ans = min(f[rt][0], f[rt][1]);
点击查看代码
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
struct T {
int v, nx;
} g[N << 1];
int h[N], idx, f[N][2];
bool st[N];
void add(int u, int v) {
g[++idx] = {v, h[u]}, h[u] = idx;
}
void dfs(int u) {
f[u][0] = 0, f[u][1] = 1;
for (int i = h[u]; i; i = g[i].nx) {
int v = g[i].v;
dfs(v);
f[u][0] += f[v][1];
f[u][1] += min(f[v][0], f[v][1]);
}
}
int main() {
int n, u, v, k;
while (~scanf("%d", &n)) {
memset(h, 0, sizeof(h)), idx = 0, memset(st, 0, sizeof(st));
for (int i = 1; i <= n; i++) {
scanf("%d:(%d)", &u, &k);
while (k--)
scanf("%d", &v), add(u, v), st[v] = 1;
}
int rt = 0;
while (st[rt]) rt++;
dfs(rt);
printf("%d\n", min(f[rt][0], f[rt][1]));
}
return 0;
}