题目描述
无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为 Wi， 每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v)，若它们的距离为 2，则它们之间会产生Wu×Wv的联合权值。
请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
输入
第一行包含 1 个整数 n。
接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点 之间有边相连。
最后 1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示 图 G 上编号为 i 的点的权值为Wi。
输出
输出共 1 行，包含 2 个整数，之间用一个空格隔开，依次为图 G 上联合权值的最大值 和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对 10007 取余。
样例输入
5
1 2
2 3
3 4
4 5
1 5 2 3 10
样例输出
20 74
对于 30%的数据，1 < n ≤ 100；
对于 60%的数据，1 < n ≤ 2000；
对于 100%的数据，1 < n ≤ 200,000，0 < Wi ≤ 10,000。
题解
图论题。
70分做法：两点之间距离为2，那么我们很容易想到枚举中间点，将中间点向外连出的所有的点两两配对，求出最大值和总和。
100做法：在70分的做法基础上，对于每个中间点，减少一次对连边的枚举。在遍历连边的时候，求出连出点的最大值和次大值，便可更新全局最大值。考虑总和，设中间点为u，它连向的点分别为v1，v2 .....
那么这些点对u的贡献可以表示为：ΣΣvi*vj ( i ≠ j ) = Σ （ vi * Σvj ） ( i ≠ j ) = Σ vi*( Σvj - vi ) = ( Σvi )2 - Σvi2 ， 即 和的平方减平方和。
注意无向图要开2倍大小。无限TLE
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=200000+50; const int mod=10007; int fir[maxn],to[2*maxn],nex[2*maxn],ecnt; ll n,u,v,w[maxn],maxx,ans,sum[maxn],a[maxn]; void add_edge(int u,int v){ nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v; } template<typename T>void read(T& aa){ char cc; ll ff;aa=0;cc=getchar();ff=1; while((cc<'0'||cc>'9')&&cc!='-') cc=getchar(); if(cc=='-') ff=-1,cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); aa*=ff; } void change(ll x,ll &m1,ll &m2){ if(x>=m1) m2=m1,m1=x; if(x<m1&&x>=m2) m2=x; } void work(int x){ ll sum=0,tot=0,m1=0,m2=0; for(int e=fir[x];e;e=nex[e]){ int v=to[e]; change(w[v],m1,m2); sum+=w[v]; tot+=w[v]*w[v]; } sum=sum*sum; maxx=max(maxx,m1*m2); ans=(ans+sum-tot)%mod; } int main(){ read(n); for(int i=1;i<n;i++){ read(u),read(v); add_edge(u,v); add_edge(v,u); } for(int i=1;i<=n;i++) read(w[i]); for(int i=1;i<=n;i++) work(i); cout<<maxx<<" "<<ans<<endl; return 0; }