题目描述 Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参与舞会。
输入 第一行一个整数N。(1<=N<=3000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。
输出 输出最大的快乐指数。
样例输入
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0样例输出
5一道因缺思厅的题目(我想问的是为什么，职员不愿意看到自己的上司，杨子曰：舞会是一个拍上司马屁的好机会呀！） 好，佷显然职员之间形成了一棵树的关系，所以很容易想到使用——树形DP 杨子曰：几乎所有树形DP，f[i][j]的第一维都表示以i为根节点的这棵子树 那第二维呢？对于这道题目而言，每个职员无非就是两种情况——取或不取，So，杨子曰：f[i][0/1]表示第i名职员取或不取时，以i为根结点的这棵子树的最大快乐指数 状态一出来，转移就很简单了，f[i][0]和f[i][1]分开来更新，如果i不取，那么他的儿子都可以取（也可以不取，搞个max），也就是说f[i][0]=sigma(max(f[son][1],f[son][0])) 再说f[i][1],当你取了i以后，他的儿子都不能选，So，f[i][1]=sigma(f[son][0]) 转移也被搞定了，巴特（BUT）还有一个严重的问题，算f[i][0/1]的时候，都要算好他的儿子，那按什么顺序更新呢，相信有人也想到了——DFS OK，完事
破天荒pascal代码：
var l:array[1..30000,0..3000]of longint; f:array[1..30000,0..1]of longint; a:array[1..30000]of longint; b:array[1..30000]of boolean; i,j,n,x,y:longint; function max(a,b:longint):longint; begin if a>b then exit(a); exit(b); end; procedure dfs(x:longint); var i,s:longint; begin if l[x,0]=0 then exit; for i:=1 to l[x,0] do dfs(l[x,i]); s:=0; for i:=1 to l[x,0] do s:=s+f[l[x,i],0]; f[x,1]:=s+a[x]; s:=0; for i:=1 to l[x,0] do s:=s+max(f[l[x,i],0],f[l[x,i],1]); f[x,0]:=s; end; begin read(n); for i:=1 to n do b[i]:=false; for i:=1 to n do l[i,0]:=0; for i:=1 to n do read(a[i]); for i:=1 to n-1 do begin read(x,y); inc(l[y,0]); l[y,l[y,0]]:=x; end; read(x,y); for i:=1 to n do if l[i,0]=0 then begin f[i,1]:=a[i]; f[i,0]:=0; end; for i:=1 to n do for j:=1 to l[i,0] do b[l[i,j]]:=true; for i:=1 to n do if not b[i] then break; dfs(i); write(max(f[i,1],f[i,0])); end.于TJQ高层小区 未经作者允许，严禁转载：https://blog.csdn.net/HenryYang2018/article/details/79758886
