描述
huyichen世子事件后，xuzhenyi成了皇上特聘的御前一品侍卫。
皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是xuzhenyi手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
帮助xuzhenyi布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
格式
输入格式
输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
输出格式
输出文件仅包含一个数，为所求的最少的经费。
提示
如图
题意： 有一颗树， 每个节点是一个宫殿， 并且有个花费。 然后要驻扎人。 如果一个节点进驻了， 相邻的点，都会被监控。 问监控所有节点的最少花费。
思路： 树形DP
对与每个节点， 有三种状态
1、进驻人
2、不进驻，但是儿子节点进驻了人。
3、不进驻，但是父亲节点进驻了人。
叶子节点的 dp[i][1] = Cost[i]; dp[i][2] = Cost[i]; dp[i][3] = 0;
而对于非叶子节点， dp[i][1] = 每个儿子（状态1，2，3）的最小花费 的总和 + cost[i]； 无论儿子节点是进驻人， 还是被他的儿子监控，或者等这i监控都可行
dp[i][2] = 每个儿子（状态1，2）的最小花费的总和， 并且该总和必须有一个儿子是进驻人的。 否则 i 节点不能被任意儿子监控。
dp[i][3] = 每个儿子(状态1， 状态2）的最小花费总和。i节点由i的父亲监控。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
//树形DP
const int V = 1500 + 5;
const int MaxN = 120 + 5;
const int mod = 10000 + 7;
const __int64 INF = 0x7FFFFFFFFFFFFFFFLL;
const int inf = 0x3fffffff;
int dp[V][3]; //dp[i][0~2]表示 第i个节点被自己，儿子，父亲监控的最小费用
int n, C[V];
bool map[V][V], vis[V];
void Tree_DP(int index) {
int i, j, k;
vector<int> v;
vis[index] = true;
for(i = 1; i <= n; ++i) {
if(!vis[i] && map[index][i]) {
v.push_back(i);
Tree_DP(i);
}
}
if(v.size() == 0) {
dp[index][0] = C[index];
dp[index][1] = C[index];
dp[index][2] = 0;
}
else {
int sum = 0, sum1 = 0, flag = 0, dis = inf;
for(i = 0; i < v.size(); ++i) {
sum += min(min(dp[v[i]][0], dp[v[i]][1]), dp[v[i]][2]);
if(dp[v[i]][0] > dp[v[i]][1])
sum1 += dp[v[i]][1];
else {
sum1 += dp[v[i]][0];
flag = 1;
}
dis = min(dis, abs(dp[v[i]][0] - dp[v[i]][1]));
}
dp[index][0] = sum + C[index];
dp[index][1] = sum1;
if(!flag)
dp[index][1] += dis;
dp[index][2] = sum1;
}
}
int main() {
int i, j;
scanf("%d", &n);
for(i = 1; i <= n; ++i) {
int a, b, m;
scanf("%d%d%d", &a, &b, &m);
C[a] = b;
for(j = 1; j <= m; ++j) {
int c;
scanf("%d", &c);
map[c][a] = true;
map[a][c] = true;
}
}
Tree_DP(1);
// for(i = 1; i <= n; ++i)
// printf("%d %d %d %d\n", i, dp[i][0], dp[i][1], dp[i][2]);
printf("%d\n", min(dp[1][0], dp[1][1]));
}