【问题描述】

　　Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

【输入】

　　第一行一个整数N。(1<=N<=6000)

　　接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

　　接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

　　最后一行输入0,0。

【输出】

　　输出最大的快乐指数。

【算法分析】

　　类似于0-1背包的树形DP基础题，状态转移详见代码。

【程序代码】

1 var a,fa:array[1..6000] of longint; 2     f:array[1..6000,0..1] of longint; 3     s:array[1..6000] of longint; 4     i,j,k,n,m,ans,u,v:longint; 5 function max(x,y:longint):longint; 6 begin 7     if x>y then exit(x) else exit(y); 8 end; 9 procedure dp(x:longint);10 var i:longint;11 begin12     if s[x]=0 then begin f[x,0]:=0; f[x,1]:=a[x]; exit; end;13     for i:=1 to n do if fa[i]=x then14     begin15         dp(i);16         inc(f[x,0],max(f[i,1],f[i,0]));17         inc(f[x,1],f[i,0]);18     end;19 end;20 begin21     readln(n);22     for i:=1 to n do readln(a[i]);23     for i:=1 to n-1 do24     begin25         readln(u,v);26         fa[u]:=v;27         inc(s[v]);28     end;29     readln(u,v);30     for i:=1 to n do if fa[i]=0 then k:=i;31     for i:=1 to n do f[i,1]:=a[i];32     dp(k);33     writeln(max(f[k,1],f[k,0]));34 end.

 声明：本博文为博主原创博文，未经允许请勿转载。