【解题报告】舞会

题目来源：vijos1706.

这题比较简单。对于任意一棵以v为根的子树，要么上司v上去，要么v的下属们上去，显然搞笑值是负的的家伙们只要坐着看就好了（笑）。设f[v,1]为以v为根节点的子树有下属上台的最大搞笑值，f[i,2]为以v为根节点的子树只有上司上台的最大搞笑值。则状态转移方程如下：(s代表v的子节点个数) $$f[v,1]=\sum _{i=1}^{s}max(f[ch[v,i],1],f[ch[v,i],2])$$（因为上司他不上去，所以下属们想怎样都可以） $$f[v,2]=a[v]+\sum _{i=1}^{s}max(f[ch[v,i],1],0)$$（上司上去了，下属们只可以派出自己的小喽啰） 觉得写得好的话，就点个赞让我知道一下呗~ AC代码：

program vijos1706; var n,i,x:integer; a:array[1..5000]of longint; ch:array[1..5000,0..4999]of integer;//ch means child. f:array[1..5000,1..2]of longint;//1 means child,2 means self. function max1(a,b:longint):longint; begin if(a>b)then exit(a); exit(b); end; procedure dp(v:integer); var max_c,max_s:longint;//max_c是有下属上去的最大值，max_s 是自己上去的最大值 i:integer; begin if(ch[v,0]=0)then exit; for i:=1 to ch[v,0] do dp(ch[v,i]); max_c:=0; for i:=1 to ch[v,0] do if(max1(f[ch[v,i],1],f[ch[v,i],2])>0)then inc(max_c,max1(f[ch[v,i],1],f[ch[v,i],2] )); f[v,1]:=max_c; max_s:=0; for i:=1 to ch[v,0] do if(f[ch[v,i],1]>0)then inc(max_s,f[ch[v,i],1]); f[v,2]:=max_s+a[v]; end; begin readln(n); for i:=1 to n do read(a[i]); for i:=2 to n do begin readln(x); inc(ch[x,0]); ch[ x,ch[x,0] ]:=i; end; for i:=1 to n do if(ch[i,0]=0)then begin f[i,2]:=a[i]; f[i,1]:=-maxlongint; end; dp(1); writeln(max1(f[1,1],f[1,2])); end.

喂喂，搞不懂怎么一直待审核······