联合权值
描述
无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为 WiWi， 每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v)，若它们的距离为 2，则它们之间会产生WuWu×WvWv的联合权值。
请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
格式
输入格式
第一行包含 1 个整数 n。
接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点 之间有边相连。
最后 1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示 图 G 上编号为 i 的点的权值为WiWi。
输出格式
输出共 1 行，包含 2 个整数，之间用一个空格隔开，依次为图 G 上联合权值的最大值 和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。
限制
对于 30%的数据，1 < n ≤ 100；
对于 60%的数据，1 < n ≤ 2000；
对于 100%的数据，1 < n ≤ 200,000，0 < WiWi ≤ 10,000。
解题报告：
刚开始的时候，是直接想的暴力，用一个O(n^3)然后我想我一定是疯了，200000，数组也大的不行，就把电脑弄死机了。。。正在考试，学校的电脑一关机就什么都没有了，于是，苦逼的我只好重新把第一题写一遍，还好简单。可接下来，我就陷入了想第二题的深渊，无法自拔，看出他是一棵树后，开始学着树规编，可是树规也没学好，还不是特别熟悉，最后还剩半个小时，算了算了，写暴力。。啊，暴力还没有调出来，就交卷了。
所以，要加快做题速度。
正解：首先枚举每一个点，找他周围的最大与第二大的点，相乘的联合权值则为以这个点为中心的最大值，最后把所有点的最大权值扫一遍，然后就得到ans2.至于权值之和，我们举一个例子：
i 这个点连了 1 2 3 三个点 ，那么权值之和即：w1*w2+w1*w3+w2*w3,技巧来了，根据乘法分配律，原式=w1*0+w2*w1+w3*(w1+w2)
根据这个，可以设一个数组存括号内的累和，然后与当前相乘，加入ans1；
代码如下：
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=,inf=;
int n,ans,maxx;
int m1[maxn],m2[maxn],a[maxn],b[maxn],w[maxn];
long long s[maxn],s2[maxn],sum;
void doit(int x,int y)
{
if (m1[x]==) m1[x]=w[y];
else if (w[y]>m2[x])
{
if (w[y]>m1[x]){
m2[x]=m1[x];
m1[x]=w[y];
}else{
m2[x]=w[y];
}
}
s[x]=(s[x]+w[y]*s2[x])%inf;
s2[x]+=w[y];
}
int main()
{
freopen("link.in","r",stdin);
freopen("link.out","w",stdout);
cin>>n;
for (int i=;i<=n-;i++)
scanf("%d%d",&a[i],&b[i]);
for (int i=;i<=n;i++)
scanf("%d",&w[i]);
for (int i=;i<=n;i++)
{
int x=a[i],y=b[i];
doit (x,y);
doit (y,x);
}
for (int i=;i<=n;i++)
{
if (m1[i]*m2[i]>maxx) maxx=m1[i]*m2[i];
ans=(ans+s[i])%inf;
}
cout<<maxx<<" "<<(ans*)%inf;
return ;
}
值得注意的是：ans最后要乘2，因为有两个方向，另外，取mod 也很重要，特别是最后输出的时候。
我认为在这么多方法中，这个是最简单而易懂的。