Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。
输入文件中数据表示一棵树，描述如下：
第一行 N，表示树中结点的数目。
第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。
对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。
输出文件仅包含一个数，为所求的最少的士兵数目。
例如，对于如右图所示的树：
答案为1（只要一个士兵在结点1上）。
【输入样例2】Strategi.in
5
3 3 1 4 2
1 1 0
2 0
0 0
4 0
【输出样例2】Strategi.out
2
树型dp.......
设状态我们考虑两点：
1：尽量不与父节点相关；
2：保证所有的路要被了望到。
先考虑第二点，已知一条路有两个节点，如果其中一个节点不选，另一个节点必须选！所以想到选和不选的情况；设出f[t,0]和f[t,1]，易列出方程;
g[gen,0]:=g[gen,0]+g[f[k,1],1]; g[gen,1]:=g[gen,1]+min(g[f[k,1],1],g[f[k,1],0]);
那么第一点手到擒来！AC！
标程（请勿抄袭）：
var g:array[0..100000,0..1] of longint; f:array[0..100000,1..2] of longint; q:array[0..100000] of longint; i,j,k,m,n,o,p,l,s,t,x,y,gen:longint; procedure insert(x,y:longint); begin inc(t); f[t,1]:=y; f[t,2]:=q[x]; q[x]:=t; end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure dg(gen:longint); var k:longint; begin k:=q[gen]; while k<>0 do begin dg(f[k,1]); g[gen,0]:=g[gen,0]+g[f[k,1],1]; g[gen,1]:=g[gen,1]+min(g[f[k,1],1],g[f[k,1],0]); k:=f[k,2]; end; inc(g[gen,1]); end; begin readln(n); for i:=1 to n do begin read(x); if i=1 then gen:=x; read(s); for j:=1 to s do begin read(y); insert(x,y); end; end; dg(gen); writeln(min(g[gen,0],g[gen,1])); end.
