这道题的难点在于状态怎么设计
这道题要求全部都是安全的，所以我们做的时候自底向上每一个结点都要是安全的
结合前一题当前结点选和不选，我们可以分出四种情况出来
选 安全
选 不安全
不选 安全
不选 不安全
显然选 不安全是不可能的，那么就去掉
所以我们就可以设计状态为
表示i放人且安全
表示i不放人且安全
表示i不放人且不安全
那么状态转移方程最关键的就是怎么保证回溯的时候都是安全的。
我们只考虑以u为结点的子树，不考虑i的父亲
我们要让u的子树除了u以外全部是安全的，u自己安全和不安全分开讨论
对于 
， u放人且安全
那么显然这时儿子无论如何都是安全的（就算原来他是不安全的）
那么有
这里v是u的儿子，这时三种情况都可以，取最小
对于
i不放人且不安全
那么为了保证u不安全肯定儿子不能放人，而这时我们要保证
儿子都安全，所以
对于
i不放人且安全
儿子一定要安全的话有
但是要保证u安全，v中至少有一个放人
这就比较麻烦了，我们要专门来判断v中有没有放人
如果没有的话，就加上
也就是以最小的费用使一个儿子从不放人到放人
最后还有一个小细节，之前我写树形dp搜到叶子都直接return的
这里不行，因为这时
是不存在的（不考虑u的父亲）
所以这时要把
初始化为最大值（代码中体现为最后加上
）
#include<cstdio>
#include<vector>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 2123;
int f[3][MAXN], a[MAXN], b[MAXN], n;
vector<int> g[MAXN];void dfs(int u)
{f[0][u] = a[u]; f[1][u] = f[2][u] = 0; int mint = 1e8, ok = 0;REP(i, 0, g[u].size()){int v = g[u][i];dfs(v);f[0][u] += min(f[0][v], min(f[1][v], f[2][v]));f[1][u] += min(f[0][v], f[1][v]);if(f[0][v] <= f[1][v]) ok = 1;mint = min(mint, f[0][v] - f[1][v]);f[2][u] += f[1][v];}if(!ok) f[1][u] += mint;
} int main()
{scanf("%d", &n);REP(i, 1, n + 1) {int u, k, son; scanf("%d", &u);scanf("%d%d", &a[u], &k);REP(j, 0, k){scanf("%d", &son);g[u].push_back(son);b[son] = 1;} }REP(i, 1, n + 1)if(!b[i]){dfs(i);printf("%d\n", min(f[0][i], f[1][i]));break;}return 0;
}