noip2014聯合權值

http://codevs.cn/problem/3728/

我們要做的是計算距離為2的有序對權值之和及最大值，最大值好弄，但一一枚舉是不可行的，因為n<=200000，我們可以預處理一下，每次讀入邊的時候我們把與當前頂點有邊相連的所有點的權值中的最大值及次大值保存起來，然后用個O(n)時間就可以計算出來。至于權值和，我們可以這樣，用s[i]存儲與節點i相連的節點的權值和，枚舉每條邊(u,v)，sigma（(s[u]-w[v])*w[v]+(s[v]-w[u])*w[u])mod 1007 即是答案。

?

?

typeedge=recordu,v:longint;end;
varn,i,j,ans1,ans2,u,v:longint;s:array[1..200000]of int64;w,max1,max2:array[1..200000]of longint;e:array[1..200000]of edge;
procedure work(x:longint;var a,b:longint);
beginif x>a then beginb:=a; a:=x;endelseif x>b then b:=x;
end;
beginreadln(n);for i:=1 to n-1 do readln(e[i].u,e[i].v);for i:=1 to n do read(w[i]);for i:=1 to n-1 do begin u:=e[i].u; v:=e[i].v;inc(s[u],w[v]);inc(s[v],w[u]);work(w[v],max1[u],max2[u]);work(w[u],max1[v],max2[v]);end;for i:=1 to n do if max1[i]*max2[i]>ans1 then ans1:=max1[i]*max2[i];for i:=1 to n-1 dobeginu:=e[i].u; v:=e[i].v;ans2:=(ans2+(s[u]-w[v])*w[v] mod 10007)mod 10007;ans2:=(ans2+(s[v]-w[u])*w[u] mod 10007)mod 10007;end;writeln(ans1,' ',ans2);
end.

?