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。 再注意一下细节，此题便做完了。 ```cpp #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); } ```