树形动规_(没有上司的晚会)

没有上司的晚会(Ural)
party.pas/c/cpp
【问题描述】
有个公司要举行一场晚会。
为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司（上司的上司，上司的上司的
上司……都可以邀请）。
每个参加晚会的人都能为晚会增添一些气氛值，求一个邀请方案，使气氛值的和最大。
【输入格式】
第 1 行一个整数 N（1<=N<=6000）表示公司的人数。
接下来 N 行每行一个整数。第 i 行的数表示第 i 个人的气氛值 x(-128<=x<=127)。
接下来每行两个整数 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
【时间限制】
1s
【空间限制】
64M

//----------------------------------------------------------------------------------------------

分析:与上一题(战略游戏)几乎一样,不多说.

code:

type  edge=record
      v,n:longint;
end;
const maxn=6001;
var   e:array[0..maxn] of edge;
      r,h,s:array[0..maxn] of longint;
      f:array[0..maxn,0..1] of longint;
      n,i,u,v,root,cnt:longint;


      procedure add(u,v:longint);
      begin
            inc(cnt);
            e[cnt].v:=v;
            e[cnt].n:=h[u];
            h[u]:=cnt;
      end;

      function max(a,b:longint):longint;
      begin
            if a>b then exit(a); exit(b);
      end;

      procedure DP(u:longint);
      var   v,p:longint;
      begin
            f[u,0]:=0;
            f[u,1]:=s[u];
            p:=h[u];
            while p<>0 do
            begin
                  v:=e[p].v;
                  DP(v);
                  inc(f[u,1],f[v,0]);
                  inc(f[u,0],max(f[v,0],f[v,1]));
                  p:=e[p].n;
            end;
      end;


begin
      assign(input,'party.in'); reset(input);
      assign(output,'party.out'); rewrite(output);

      readln(n);
      for i:=1 to n do readln(s[i]);

      while not seekeof do
      begin
            readln(u,v);
            if u+v=0 then break;
            add(v,u);
            inc(r[u]);
      end;

      for i:=1 to n do
         if r[i]=0 then
         begin
               root:=i;
               break;
         end;

      DP(root);

      writeln(max(f[root,0],f[root,1]));

      close(input);
      close(output);
end.