记录编号	33053	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	Des.	是否通过	通过
代码语言	Pascal	运行时间	0.849 s
提交时间	2011-11-09 13:56:36	内存使用	20.85 MiB

program profitz;
uses math;
var b:array[1..100000,0..50]of longint;
    a:array[1..100000]of longint;
    f:array[1..100000,0..1]of longint;
    t,k,m,n,i,j:longint;
procedure treedp(i,p:longint);
var t,k,j:longint;
begin
if (b[i,0]=1)and(b[i,1]=p) then
  begin
    f[i,0]:=0;
    f[i,1]:=a[i];
    exit;
  end;
for t:=1 to b[i,0] do
  if b[i,t]<>p then
    treedp(b[i,t],i);
f[i,1]:=a[i];
for t:=1 to b[i,0] do
  if b[i,t]<>p then
    begin
      f[i,1]:=f[i,1]+f[b[i,t],0];
      f[i,0]:=f[i,0]+max(f[b[i,t],0],f[b[i,t],1]);
    end;
end;
begin
assign(input,'profitz.in');
reset(input);
assign(output,'profitz.out');
rewrite(output);
readln(n);
for t:=1 to n do
  readln(a[t]);
for t:=1 to n-1 do
  begin
    readln(i,j);
    inc(b[i,0]);
    b[i,b[i,0]]:=j;
    inc(b[j,0]);
    b[j,b[j,0]]:=i;
  end;
treedp(1,0);
writeln(max(f[1,0],f[1,1]));
close(output);
end.