求树上距离为二的点对权积之最值、和。
70pts：枚举每个点，bfs两层求和求最值和和。
100pts：枚举每个点，先统计所有可达节点的权值和，再枚举可达点求权值和
第二种做法较第一种的优化：
a1*a2+a1*a3+a1*a4+..a2*a1+a2*a3+...
=>a1*(sum-a1)+a2*(sum-a2)+...
好巧妙啊
要注意的一点：小心过程量爆int！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 8 int read(){ 9 int a = 0;char l = ' ',c = getchar(); 10 while(c < '0'||c > '9')l = c,c = getchar(); 11 while('0' <= c&&c <= '9')a = a*10+c-'0',c = getchar(); 12 if(l == '-')return -a;return a; 13 } 14 15 const int Maxn = 2e6+10; 16 17 struct Edge{ 18 int to,ne; 19 }edges[Maxn<<1]; 20 21 int first[Maxn]; 22 int w[Maxn]; 23 int n,m,ans,tot,top,cnte,x; 24 25 void add_edge(int fr,int to){ 26 edges[++cnte] = (Edge){to,first[fr]}; 27 first[fr] = cnte; 28 } 29 30 int main(){ 31 // freopen("x.in","r",stdin); 32 // freopen("x.out","w",stdout); 33 n = read(); 34 for(int i = 1;i < n;i++){ 35 int u,v; 36 u = read(),v = read(); 37 add_edge(u,v); 38 add_edge(v,u); 39 } 40 for(int i = 1;i <= n;i++)w[i] = read(); 41 for(int i = 1;i <= n;i++){ 42 long long s = 0; 43 int m1 = 0,m2 = 0; 44 for(int j = first[i];j;j = edges[j].ne){ 45 int u = edges[j].to; 46 s += w[u]; 47 if(w[u] > m1)m2 = m1,m1 = w[u]; 48 else m2 = max(m2,w[u]); 49 } 50 ans = max(ans,m1*m2); 51 for(int j = first[i];j;j = edges[j].ne) 52 x = w[edges[j].to],tot = (tot+x*(s-x))%10007; 53 } 54 cout << ans << ' ' << tot; 55 return 0; 56 }