记录编号	33087	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	0.876 s
提交时间	2011-11-09 14:46:53	内存使用	21.48 MiB

program profitz;
var
  f:array[1..100000,0..1]of int64;
  g:array[1..100000,0..50]of longint;
  n,i,ans,x,y:longint;
  a:array[1..100000]of longint;
function max(a,b:int64):int64;
begin
  if a>b then
    exit(a)
  else
    exit(b)
end;
procedure dp(v,father:longint);
var
  i:longint;
begin
  if (g[v,0]=1)and(g[v,1]=father) then
  begin
    f[v,1]:=a[v];
    f[v,0]:=0
  end
  else
  begin
    for i:=1 to g[v,0] do
      if g[v,i]<>father then
        dp(g[v,i],v);
    f[v,1]:=a[v];
    f[v,0]:=0;
    for i:=1 to g[v,0] do
      if g[v,i]<>father then
      begin
        f[v,1]:=f[v,1]+f[g[v,i],0];
        f[v,0]:=f[v,0]+max(f[g[v,i],0],f[g[v,i],1])
      end
  end
end;
begin
  assign (input,'profitz.in');
  reset (input);
  assign (output,'profitz.out');
  rewrite (output);
    readln (n);
    for i:=1 to n do
      readln (a[i]);
    for i:=1 to n-1 do
    begin
      readln (x,y);
      inc(g[x,0]);
      g[x,g[x,0]]:=y;
      inc(g[y,0]);
      g[y,g[y,0]]:=x;
    end;
    dp(1,0);
    ans:=max(f[1,0],f[1,1]);
    writeln (ans);
  close (input);
  close (output)
end.