NOIp提高组2014 联合权值————dp贪心

题解：本题主要考查dp/贪心。 简要题意：一棵树，编号为$i$的点的权值为$W_i$​，每条边的长度均为$1$。对于图$G$上的点对$(u,v)$，若它们的距离为$2$，则它们之间会产生$W_v\times W_u$的联合权值。求最大的联合权值和联合权值总和。 1.dp/贪心：其实本题换一种思想就很简单，因为距离为$2$的点一定有一个中间点，所以枚举每一个中间点，取任意两个联通的点，找到最大值和次大值，相乘就可以得到最大联合权值。将所有的值加一下，注意因为两点可以颠倒位置，所以再乘2，输出就可以了。注意联合权值和要取模，最大的联合权值不能取$!!!$ 代码如下：

#include<iostream> #include<algorithm> using namespace std; int mod=10007; struct E { int start,to; }e[666666]; int h[666666],a[666666]; int n,P,max1,max2,maxn,ans,sum; void add(int start,int to) { e[++P].to=to; e[P].start=h[start]; h[start]=P; } int main() { cin>>n; for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; add(x,y);add(y,x); } for(int i=1;i<=n;i++)cin>>a[i]; for(int j=1;j<=n;j++) { max1=0;max2=0;sum=0; for(int i=h[j];i;i=e[i].start) { int k=e[i].to; if(a[k]>max1){max2=max1;max1=a[k];} else if(a[k]>max2)max2=a[k]; ans=(ans+sum*a[k])%mod; sum=(sum+a[k])%mod; } maxn=max(maxn,max1*max2); } ans=(ans*2)%mod; cout<<maxn<<" "<<ans; return 0; }