題目大意，有一些節點，節點間有路，節點上放哨兵可以監視和此節點直接連接的節點。求用最少的哨兵，監視所有的節點，沒有盲區。。。。
其實一看就知道是一個dp，01背包。每個節點上只有兩種情況，放或者不放，按平時來說就是簡單的dp，但是這次是一個樹，所以要在樹上做01背包。
狀態方程很好想：
dp【i】【0】表示第i點不放哨兵
dp【i】【1】表示第i點放哨兵
那麼我們知道：
dp【i】【0】 = dp【j0】【1】 + dp【j1】【1】 + dp【j2】【1】+dp【j3】【1】。。。。（j1，j2， j3。。 jm為i的孩子，也就是說如果i不放，那麼他的孩子必須放）。
dp【i】【1】 = min（dp【j0】【1】， dp【j0】【0】） + min（dp【j1】【1】， dp【j1】【0】）。。。。（j1，j2， j3 。。jm為i的孩子，也就是說如果i放，那麼他的孩子必可放可不放，求最小值）。
有了狀態方程代碼就好些了
如下：
[cpp]
#include<iostream>
using namespace std;
#define nMax 1505
#define inf 0x3ffffff
int son[nMax], brother[nMax];
bool father[nMax];
int dp[nMax][2];
int n;
void dfs(int root)
{
dp[root][0] = 0;
dp[root][1] = 1;
int k = son[root];
while (k != -1)
{
dfs(k);
dp[root][0] += dp[k][1];//如果不放，孩子必放
dp[root][1] += min(dp[k][0], dp[k][1]);//如果放，孩子可放可不放，求最小值
k = brother[k];
}
}
int main()
{
while (scanf("%d", &n) != EOF)
{
int root;
memset(son, -1, sizeof(son));
memset(father, false, sizeof(father));
int u, vNum, v;
for (int i = 0; i < n; ++ i)
{
scanf("%d:(%d)", &u, &vNum);
for (int j = 0; j < vNum; ++ j)
{
scanf("%d", &v);
brother[v] = son[u];//同一個父親節點下的上一個兄弟
son[u] = v;//u的孩子
father[v] = true;//判斷是否有父親，求根節點
}
}
for (int i = 0; i < n; ++ i)
{
if (!father[i])
{
root = i;
break;
}
}
dfs(root);
printf("%d\n", dp[root][0] < dp[root][1] ? dp[root][0] : dp[root][1]);
}
return 0;
}
