caioj 1111 树形动态规划（TreeDP）6： 皇宫看守 (状态设计)

这道题的难点在于状态怎么设计
这道题要求全部都是安全的，所以我们做的时候自底向上每一个结点都要是安全的
结合前一题当前结点选和不选，我们可以分出四种情况出来
选 安全
选 不安全
不选 安全
不选 不安全

显然选 不安全是不可能的，那么就去掉
所以我们就可以设计状态为
表示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
", min(f[0][i], f[1][i]));
			break;
		}

	return 0;	
}