一、算法分析
树形\(dp\)，与没有上司的舞会具有对称性
没有上司的舞会题解地址 https://www.acwing.com/solution/acwing/content/7920/
没有上司的舞会：每条边上最多选择一个点，求最大权值
战略游戏：每条边上最少选择一条点，求最小权值
显然我们不能 暴力枚举 树中所有结点 选(1) 与 不选(0) 的状态（时间复杂度 为 \(O(2^n)\)）
因此，会想到采用 分治 思想：
考虑以结点 \(u\) 为 根节点 的子树，该子树所有的 方案，可以由当前结点 放 或 不放哨兵 进行划分
这也是一种 状态机模型，我简略的绘制一下这个状态机：
状态表示
\(f[u][0]\)：所有以\(u\)为根的子树中选择，并且不选\(u\)这个点的方案
\(f[u][1]\)：所有以\(u\)为根的子树中选择，并且选\(u\)这个点的方案
属性
\(Min\)
状态计算
当前\(u\)结点不选，子结点一定选 \(f[u][0]=∑(f[s_i][1])\)
当前\(u\)结点选，子结点一定可选可不选 \(f[u][1]=∑min(f[s_i][0],f[s_i][1])\)
时间复杂度 \(O(n)\)
二、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1510; //因为题目明确是有向图，无需M=N*2
int h[N], e[N], ne[N], idx; //邻接表
int f[N][2];
/**
集合： 以结点i为 根节点 的子树，在 i 上放置哨兵(1) 和不放哨兵(0) 的方案
状态表示： 方案中，放置的哨兵数量 最少
状态计算：
*/
bool st[N]; //用于判断是不是根节点
//邻接表模板
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
//状态初始化
f[u][0] = 0, f[u][1] = 1;
//遍历每一条出边
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
dfs(j);
//状态转移方程
f[u][0] += f[j][1];//节点u不放置哨兵，那么一定要从某一邻接节点放置哨兵
f[u][1] += min(f[j][0], f[j][1]);//如果节点u放置了哨兵，那么邻接节点可以选择放置或者不放置
}
}
int main() {
//n组数据
int n;
//不断读入数据
while (cin >> n) {
//多组数据，清空邻接表
memset(h, -1, sizeof h), idx = 0;
//清空状态数组
memset(st, 0, sizeof st);
//n个节点
for (int i = 1; i <= n; i++) {
int x, m;
scanf("%d:(%d)", &x, &m);//scanf可以按格式读入数据
while (m--) {
int y;
cin >> y;
//添加一条x->y的有向边
//数据样例：1出发可以到达2,3;说明是有向图
add(x, y);
//标识y不是根
st[y] = true;
}
}
//有向图，需要找到出根
int root = 0;
while (st[root]) root++;
//从根开始
dfs(root);
//输出 两个结果取个 min
printf("%d\n", min(f[root][0], f[root][1]));
}
return 0;
}