自己网站上做淘宝搜索,锦州网站建设案例,黄石做网站,珠宝网站开发的背景http://codevs.cn/problem/3728/ 我们要做的是计算距离为2的有序对权值之和及最大值#xff0c;最大值好弄#xff0c;但一一枚举是不可行的#xff0c;因为n200000#xff0c;我们可以预处理一下#xff0c;每次读入边的时候我们把与当前顶点有边相连的所有点的权值中…http://codevs.cn/problem/3728/ 我们要做的是计算距离为2的有序对权值之和及最大值最大值好弄但一一枚举是不可行的因为n200000我们可以预处理一下每次读入边的时候我们把与当前顶点有边相连的所有点的权值中的最大值及次大值保存起来然后用个O(n)时间就可以计算出来。至于权值和我们可以这样用s[i]存储与节点i相连的节点的权值和枚举每条边(u,v)sigma(s[u]-w[v])*w[v](s[v]-w[u])*w[u])mod 1007 即是答案。 typeedgerecordu,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 xa then beginb:a; a:x;endelseif xb 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. 转载于:https://www.cnblogs.com/cxvdzxhb/p/4510452.html
