记录编号	33171	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	lizhe	是否通过	通过
代码语言	Pascal	运行时间	0.837 s
提交时间	2011-11-09 17:07:11	内存使用	20.72 MiB

program profitz;
var
  i,j,n,x,y,max:longint;
  a,t:array[1..100000]of longint;
  f:array[1..100000,0..1]of longint;
  g:array[1..100000,1..50]of longint;
procedure init;
begin
  assign(input,'profitz.in');
  reset(input);
  assign(output,'profitz.out');
  rewrite(output);
  read(n);
  for i:=1 to n do
    read(a[i]);
  for i:=1 to n-1 do
  begin
    read(x,y);
    inc(t[x]); g[x,t[x]]:=y;
    inc(t[y]); g[y,t[y]]:=x
  end
end;

procedure dp(v,l:longint);
var
  p,i,sum1,sum2:longint;
begin
  sum1:=0;  sum2:=0;
  for i:=1 to t[v] do
  if g[v,i]<>l then
  begin
    p:=g[v,i];
    dp(p,v);
    sum1:=sum1+f[p,0];
    if f[p,1]>f[p,0] then sum2:=sum2+f[p,1]
    else sum2:=sum2+f[p,0]
  end;
  if f[v,1]<sum1+a[v] then f[v,1]:=sum1+a[v];
  if f[v,0]<sum2 then f[v,0]:=sum2
end;

procedure print;
begin
  max:=f[1,0];
  if max<f[1,1] then max:=f[1,1];
  writeln(max);
  close(input);
  close(output)
end;

begin
  init;
  dp(1,0);
  print
end.