题目描述】
Bob特别喜欢战略游戏，但有时他不能尽快找到最优解，所以他就很伤心。现在他又有一个问题，他必须保卫一个中世纪的城市，这个城市的道路形成了一棵树。他需要在树的节点上放最少的士兵来观察所有的边。你能帮助他么？
例如右图就只需要一个士兵放在1号节点。
【输入格式】
输入文件soldier.in中有多组数据，每组数据的第一行N表示点的个数。接下来N行每行格式如下
x:(k) a1 a2 … ak（x为点的编号，k为与其相连的子节点个数，a1, a2, …, ak分别为子节点的编号）
【输出】
输出文件soldier.out，对于每组数据输出一行一个数，即最少士兵数。
【输入样例】
4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
【输出样例】
1
2
【数据规模】
0 < N<= 1500, 0 <= x < N
一道听起来就会，但是不会写的树形DP，转移方程没什么改变，就是处理的时候注意些，小心点打。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define il inline using namespace std; il int gi() { int x=0,y=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') y=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*y; } int pre[100045],cnt; struct edge { int next,to; }e[100045]; void add(int from,int to) { e[++cnt].next=pre[from]; e[cnt].to=to; pre[from]=cnt; } int f[1545][2]; void dfs(int x,int y) { f[x][1]=1; int r=pre[x]; while(r!=-1) { if(e[r].to!=y) { dfs(e[r].to,x); f[x][0]+=f[e[r].to][1]; f[x][1]+=min(f[e[r].to][0],f[e[r].to][1]); } r=e[r].next; } } int num[1545]; int main() { freopen("soldier.in","r",stdin); freopen("soldier.out","w",stdout); int n,x; while(cin>>n) { memset(f,0,sizeof(f)); cnt=0; memset(pre,-1,sizeof(pre)); for(int i=0;i<n;i++) { x=gi(); num[x]=gi(); for(int j=1;j<=num[x];j++) { int y=gi(); add(y,x); add(x,y); } } dfs(0,-1); printf("%d ",min(f[0][0],f[0][1])); } return 0; }