这个题我是用树形动规做的~
f[i,0]表示i节点被儿子所覆盖的最小点数。
f[i,1]表示i节点被自己所覆盖的最小点数。
f[i,2]表示i节点被父亲所覆盖的最小点数。
然后用递归求解，说下转移方程。
设j取遍i的所有儿子
f[i,0]:=f[j,1]+sigma(min(f[k,0],f[k,1])) k是不同于j的其他儿子
f[i,1]:=1+sigma(min(f[j,0],f[j,1],f[j,2]))
f[i,2]:=sigma(f[j,0])
初始化：(即叶子节点x)
f[x,0]:=maxx;
f[x,1]:=1;
f[x,2]:=0;
还有这个题是给的边，最好先转成以1为根节点的树的结构，用边表做的。还应注意最后输出min(f[1,0],f[1,1])。而不要找f[1,2]，因为根节点是木有父节点滴~
这样复杂度O(n^2)。
可以优化到O(n)：先用sum=sigma(min(f[j,1],f[j,0])),然后转移f[i,0]:=sum-min(f[j,1],f[j,0])+f[j,1]。据说还有贪心的？Orz......
View Code const maxx=maxlongint shr 1;type zj=record nod:longint; aft:longint;end;var n,i:longint; a,b,len:longint; et,e:array[1..20000] of zj; vt,v:array[1..10000] of longint; mark:array[1..10000] of boolean; f:array[1..10000,0..2] of longint;function min2(a,b:longint):longint;beginif a>b then exit(b) else exit(a);end;function min3(a,b,c:longint):longint;var t:longint;begin t:=maxx;if a<t then t:=a;if b<t then t:=b;if c<t then t:=c; exit(t);end;procedure add(x,y:longint);begin inc(len); e[len].nod:=y; e[len].aft:=v[x]; v[x]:=len;end;procedure addt(x,y:longint);begin inc(len); et[len].nod:=y; et[len].aft:=vt[x]; vt[x]:=len;end;procedure graphtotree(x:longint);var y,i:longint;begin mark[x]:=true; i:=v[x];while i<>0 dobegin y:=e[i].nod; i:=e[i].aft;if mark[y] then continue; addt(x,y); graphtotree(y);end;end;procedure dp(x:longint);var h:boolean; i,y,sum,tmp:longint;beginif vt[x]=0 then begin f[x,0]:=maxx; f[x,1]:=1; f[x,2]:=0; exit;end; i:=vt[x]; sum:=0; f[x,1]:=1; tmp:=0; h:=true;while i<>0 dobegin y:=et[i].nod; i:=et[i].aft; dp(y); f[x,1]:=f[x,1]+min3(f[y,0],f[y,1],f[y,2]); sum:=sum+min2(f[y,0],f[y,1]);if f[y,0]<>maxx then tmp:=tmp+f[y,0] else h:=false;end;if h then f[x,2]:=tmp else f[x,2]:=maxx; i:=vt[x]; f[x,0]:=maxx;while i<>0 dobegin y:=et[i].nod; i:=et[i].aft; f[x,0]:=min2(f[x,0],sum-min2(f[y,0],f[y,1])+f[y,1]);end;end;beginwhile true do begin readln(n); if n=-1 then break;if n=0 then continue; fillchar(v,sizeof(v),0); fillchar(vt,sizeof(vt),0); len:=0;for i:=1 to n-1 dobegin readln(a,b); add(a,b); add(b,a);end; fillchar(mark,sizeof(mark),false); len:=0; graphtotree(1); dp(1); writeln(min2(f[1,0],f[1,1]));end;end.转载于:https://www.cnblogs.com/zjerly/archive/2011/10/14/2211192.html
相关资源：JAVA上百实例源码以及开源项目