记录编号	189953	评测结果	AAAAAAATTT
题目名称	[NOIP 2014]联合权值	最终得分	70
用户昵称	Marvolo	是否通过	未通过
代码语言	Pascal	运行时间	3.461 s
提交时间	2015-09-30 20:57:45	内存使用	12.37 MiB

program zht;
var
a,a2,b,b2,c:array[1..400000] of longint;
w,mm:array[1..200000,1..2] of longint;
bj,h:array[1..200000] of longint;
i,x,y,n,s,bh,ans,cz,max,j:longint;

procedure gb(low,high:longint);
var
q,w,e,k,mid:longint;
begin
if low=high then exit;

mid:=(low+high) div 2;
gb(low,mid);
gb(mid+1,high);

q:=low;
w:=mid+1;
e:=low;

while (q<=mid) and (w<=high) do
begin
if a[q]>a[w] then begin a2[e]:=a[w];b2[e]:=b[w];inc(e);inc(w);end
else begin a2[e]:=a[q];b2[e]:=b[q];inc(e);inc(q);end;
end;

while q<=mid do
begin a2[e]:=a[q];b2[e]:=b[q];inc(e);inc(q);end;

while w<=high do
begin a2[e]:=a[w];b2[e]:=b[w];inc(e);inc(w);end;


 for k:=low to high do
begin
a[k]:=a2[k];
b[k]:=b2[k];
end;

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);
s:=s+2;
a[s-1]:=x;
b[s-1]:=y;
a[s]:=y;
b[s]:=x;
end;

for i:=1 to n do
read(c[i]);

gb(1,s);

bh:=1;

w[1,1]:=1;



for i:=2 to s do
if a[i]<>bh then begin w[bh,2]:=i-1;bh:=a[i];w[bh,1]:=i;end;
w[n,2]:=s;


for i:=1 to n do
begin
 for j:=w[i,1] to w[i,2] do
 begin
 if c[b[j]]>mm[i,1] then begin mm[i,1]:=c[b[j]];bj[i]:=b[j];end;
 h[i]:=(h[i]+c[b[j]]) mod 10007;
 end;

 for j:=w[i,1] to w[i,2] do
 if c[b[j]]>mm[i,2] then if b[j]<>bj[i] then mm[i,2]:=c[b[j]];

end;


for i:=1 to s do
begin
ans:=(ans+( ( (h[b[i]]-c[a[i]]) mod 10007)*(c[a[i]] mod 10007) mod 10007) ) mod 10007;
if (bj[b[i]]<>a[i]) and (c[a[i]]*mm[b[i],1]>max) then max:=c[a[i]]*mm[b[i],1]
else if bj[b[i]]=a[i] then if max<c[a[i]]*mm[b[i],2] then max:=c[a[i]]*mm[b[i],2];
end;
writeln(max,' ',ans);
close(input);
close(output);
end.