题目链接：http://poj.org/problem?id=1463
题意：给出一个无向图，每个节点只有一个父亲节点，可以有多个孩子节点，在一个节点上如果有一位战士守着，那么他可以守住和此节点相连的边。求最少战士数量。
解法：树形DP的入门级题目。
简单说明：f[i][0]表示以i节点为根没有战士守卫的情况，f[i][1]则表示有战士守卫
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int maxn=+;
int n;
int father[maxn],vis[maxn],f[maxn][];
void dfs(int root)
{
vis[root]=;
f[root][]=;
f[root][]=;
for (int i= ;i<n ;i++)
{
if (father[i]==root && !vis[i])
{
dfs(i);
f[root][] += f[i][];
f[root][] += min(f[i][],f[i][]);
}
}
}
int main()
{
while (cin>>n)
{
int k,a,b;
memset(vis,,sizeof(vis));
memset(f,,sizeof(f));
for (int i= ;i<n ;i++) father[i]=i;
for (int i= ;i<n ;i++)
{
scanf("%d:(%d)",&a,&k);
while (k--)
{
scanf("%d",&b);
father[b]=a;
}
}
//for (int i=0 ;i<n ;i++)
//cout<<i<<" "<<father[i]<<endl;
int sum=;
for (int i= ;i<n ;i++)
{
if (father[i]==i)
{
dfs(i);
sum += min(f[i][],f[i][]);
}
}
cout<<sum<<endl;
}
return ;
}