Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。
input：
输入文件中数据表示一棵树，描述如下：
第一行 N，表示树中结点的数目。
第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。
对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。
output：
输出文件仅包含一个数，为所求的最少的士兵数目。
input：
4
0 1 1
1 2 2 3
2 0
3 0
output：
1
分析：
树型DP：首先建树，任选一个结点为根。设要看守住以x为根的子树中所有边，x处有士兵时需要的最少士兵数为yes[x]，x处无士兵时需要的最少士兵数为no[x]。自下而上地计算每个结点的yes值和no值：一个结点的yes值等于它所有子树的yes值与no值的较小值之和再加1；no值等于它所有子树的yes值之和。根结点的yes值和no值中的较小值即为答案。【参考程序】：
#include<iostream>
using namespace std;
int now[1600],pre[3200],child[3200];
int f0[1600],f1[1600];
int v[1600];
int n;
int MIN(int a,int b)
{
if (a<b) return a;
else return b;
}
void dfs(int k)
{
v[k]=false;f0[k]=0;f1[k]=1;
while (now[k]>0)
{
if (v[child[now[k]]])
{
dfs(child[now[k]]);
f0[k]+=f1[child[now[k]]];
f1[k]+=MIN(f0[child[now[k]]],f1[child[now[k]]]);
}
now[k]=pre[now[k]];
}
}
int main()
{
scanf("%d",&n);
memset(now,-1,sizeof(now));
int c=0,a,k,b;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a,&k);
for (int i=1;i<=k;i++)
{
scanf("%d",&b);
c++;
child[c]=a;pre[c]=now[b];now[b]=c;
c++;
child[c]=b;pre[c]=now[a];now[a]=c;
}
}
memset(f0,0,sizeof(f0));
memset(f1,0,sizeof(f1));
memset(v,true,sizeof(v));
dfs(0);
int ans=MIN(f0[0],f1[0]);
printf("%d\n",ans);
return 0;
}