NOIP2014联合权值
题目大意
无向连通图G 有n 个点，n - 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i ，每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu
×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
Solution
谓的有n-1条边，n个点的无相连通图，其实就是一颗无根树。换句话说，没有一个环。所以，要是两个点同于另一个点相连，则它们不可能再有边相连，即它们之间的距离为2.
于是，思路就隐隐出来了：枚举每一个点，取其任意两个点，然后进行组合，然后两两相乘，得到最大值与他们的和。将所有值统计一下，然后注意因为和是组合出来的，所以再乘2，输出就可以了。
这里先申明一个坑点：题目只说了对和取模，没有说对最大值取模，所以要注意，如果对最大值取模就错了。
然后就是对于每一个点的问题了。如果直接组合，则n^2复杂度会TLE。我们可以使用乘法结合律和前缀和的思想。对于一个点，因为用邻接表存储，所以线性扫过所有与他相连的点，然后动态更新目前的和与目前这些点中的最大值，然后再到下一个点时，将下一个点的权值与这两个值相乘，然后做相应的处理就行了。类似于DP。
再注意一下细节，此题便做完了。
#include<bits/stdc++.h>
using namespace std;
long long w[300001];
struct edge{
int v,next;
}a[1000001];
int cnt,n,head[300001];
void add(int x,int y)
{
a[++cnt].v=y;
a[cnt].next=head[x];
head[x]=cnt;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
long long sum=0,maxn=0;
long long he,rmax;
int node;
for(int i=1;i<=n;i++)
{
node=head[i];
he=(rmax=w[a[node].v])%10007;
node=a[node].next;
for(;node;node=a[node].next)
{
sum=(sum+he*w[a[node].v])%10007;
maxn=max(maxn,rmax*w[a[node].v]);
he=(he+w[a[node].v])%10007;
rmax=max(rmax,w[a[node].v]);
}
}
printf("%lld %lld",maxn,(sum*2)%10007);
}