来自"NOCOW"

#include <iostream>
#include <fstream>
using namespace std;
const int maxn=6000+2; const int maxint=2100000000;
int F[maxn][2]; int value[maxn];
int n,root; int brother[maxn]={0},son[maxn]={0},fa[maxn]={0};
void Init()
{
     memset(F,255,sizeof(F));
     scanf("%d",&n); int i; for (i=1;i<=n;i++) scanf("%d",&value[i]);
     int a,b;
     while (1)
     {
        scanf("%d%d",&a,&b); if (a==0) break;
        fa[a]=b; brother[a]=son[b]; son[b]=a;
     }
     root=n+1; 
     for (i=1;i<=n;i++) if (fa[i]==0) {fa[i]=root; brother[i]=son[root]; son[root]=i;}
}
 
int Mdfs(int k,int flag)
{
    if (F[k][flag]!=-1) return F[k][flag];
    if (k==0) {F[k][flag]=0; return 0;}
    if (flag) F[k][flag]=Mdfs(son[k],0)+Mdfs(brother[k],1);
    else F[k][flag]=max(Mdfs(son[k],1)+value[k],Mdfs(son[k],0))+Mdfs(brother[k],0);
    return F[k][flag];
}
 
int main()
{
    Init();
    Mdfs(root,1);
    printf("%d",F[root][1]);
    return 0;
}

---

树状DP(怎么更像是记忆化dfs..?） 小心内存。。。。

var
  maxdeep,i,j,k,n,head,tail,l,p:longint;
  d,sont,e,fat:array[1..6000]of integer;
  g,son:array[1..6000,1..400]of integer;
  f:array[1..6000,0..1]of longint;
  bo:Array[1..6000]of boolean;
function max(A,b:longint):longint;
begin
  if a>b then
    maX:=a
    else
    max:=b;
end;
procedure dfs(p:longint);
var
  i:longint;
begin
  if sont[p]=0 then
    begin
      bo[p]:=true;
      exit;
    end;
  for i := 1 to sont[p] do
    begin
      if not bo[son[p,i]] then
        dfs(son[p,i]);
      f[p,0]:=max(f[son[p,i],1],f[son[p,i],0])+f[p,0];
      f[p,1]:=f[son[p,i],0]+f[p,1];
    end;
  bo[p]:=true;
end;
begin                                  
  assign(input,'input.in');reset(input);
  assign(output,'output.out');rewrite(output);
  readln(n);
  for i:=1 to n do
    begin
      readln(e[i]);
      f[i,1]:=e[i];
      f[i,0]:=0;
    end;
  readln(l,k);
  while (l<>0)and(k<>0) do
    begin
      inc(sont[k]);
      son[k,sont[k]]:=l;
      inc(fat[l]);
      readln(l,k);
    end;
  for i:=1 to n do
    if fat[i]=0 then
      begin
        dfs(i);
        writeln(max(f[i,0],f[i,1]));
        break;
      end;
end.