Description
Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。
Input
输入文件中数据表示一棵树，描述如下：
第一行 N，表示树中结点的数目。
第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。
对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。
Output
输出文件仅包含一个数，为所求的最少的士兵数目。
Sample Input
4
0 1 1
1 2 2 3
2 0
3 0
Sample Output
1
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int F[2][1510],now[1510],child[3200],next[3200];
bool vis[1510];
int n;
int Min(int x,int y)
{
return x<y?x:y;
}
void tree_dp(int k)
{
vis[k]=true; F[0][k]=0; F[1][k]=1;
while (now[k]>0)
{
if (!vis[child[now[k]]])
{
tree_dp(child[now[k]]);
F[0][k]+=F[1][child[now[k]]];
F[1][k]+=Min(F[1][child[now[k]]],F[0][child[now[k]]]);
}
now[k]=next[now[k]];
}
}
int main()
{
scanf("%d",&n);
memset(now,-1,sizeof(now));
int c=0,a,b,k;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a,&k);
for (int j=1;j<=k;j++)
{
scanf("%d",&b);
c++;
child[c]=a; next[c]=now[b]; now[b]=c;
c++;
child[c]=b; next[c]=now[a]; now[a]=c;
}
}
memset(F,0,sizeof(F));
memset(vis,false,sizeof(vis));
tree_dp(0);
printf("%d\n",Min(F[0][0],F[1][0]));
return 0;
}