题解 P1122 【最大子树和】

The_Dark_Knight · 2016-11-07 20:56:20 · 题解

看到没有pascal就来贡献一波拯救广大pascal党了。这个DP倒不是很难。深搜建树的时候可以一起做了。往下深搜，回来的时候下面的子树显然就处理干净了，如果下面子树的和小于0显然就没必要加上来了，否则就一起加上来，最大差不多也就这样子

var w,last,f,dp:array[1..20000] of longint;
    next,e:array[1..200000] of longint;
    i,j,k,m,n,p,t,u,v,max:longint;
procedure bt(c:longint);
var p,po,i,j,k:longint;
begin
    p:=last[c];dp[c]:=w[c];
    while p<>0 do
    begin
        po:=e[p];
        if po<>f[c] then
        begin
            f[po]:=c;
            bt(po);
            if dp[po]>0 then inc(dp[c],dp[po]);
            if dp[c]>max then max:=dp[c];
        end;
        p:=next[p];
    end;
end;
begin
    assign(input,'P1122.in');reset(input);
    readln(n);
    for i:=1 to n do
      read(w[i]);
    for i:=1 to n-1 do
    begin
        readln(u,v);
        e[2*i]:=v;next[2*i]:=last[u];last[u]:=2*i;
        e[2*i-1]:=u;next[2*i-1]:=last[v];last[v]:=2*i-1;
    end;
    bt(1);
    writeln(max);
end.