记录编号	233827	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	ConanQZ	是否通过	通过
代码语言	Pascal	运行时间	0.397 s
提交时间	2016-03-06 08:06:41	内存使用	5.64 MiB

 program linkb;
 uses math;
 type
  node=record
    go,last:longint;
  end;

 var
 w:array[1..400010]of node;
 v,num,head:array[1..200010]of longint;
 maxx,x,y,n,sum,tot:int64;
 i:longint;

procedure ad(x,y:longint);
begin
 inc(num[x]);
 inc(tot);
 w[tot].last:=head[x];
 w[tot].go:=y;
 head[x]:=tot;
end;

function qsum(now:longint):longint;
var
sum1,sum,i,max1,max2,ii:int64;
begin
 if num[now]<2 then exit(0);
 sum1:=0;
 sum:=0;
 max1:=0;
 max2:=0;
 i:=head[now];
 while i<>0 do
   begin
    inc(sum1,v[w[i].go]);
    if v[w[i].go]>max1 then
      begin
       max2:=max1;
       max1:=v[w[i].go];
      end
    else
    if v[w[i].go]>max2 then
      begin
       max2:=v[w[i].go];
      end;
    i:=w[i].last;
   end;
 i:=head[now];
 while i<>0 do
   begin
    sum:=(sum mod 10007+((sum1-v[w[i].go])*v[w[i].go]mod 10007))mod 10007;
    i:=w[i].last;
   end;
 maxx:=max(maxx,max1*max2);
 exit(sum);
end;

begin
  assign(input,'linkb.in');
  assign(output,'linkb.out');
  reset(input);
  rewrite(output);
  readln(n);
  for i:=1 to n-1 do
    begin
     readln(x,y);
     ad(x,y);
     ad(y,x);
    end;
  for i:=1 to n do
    begin
     read(v[i]);
    end;
  for i:=1 to n do
    begin
      sum:=(sum mod 10007+qsum(i)mod 10007)mod 10007;
    end;
  writeln(maxx,' ',sum mod 10007);
  close(input);
  close(output);
end.