无向连通图G有n个点，n-1条边。点从1到n依次编号，编号为i的点的权值为Wi ，每条边的长度均为1。图上两点(u, v)的距离定义为u点到v点的最短距离。对于图G上的点对(u, v)，若它们的距离为2，则它们之间会产生Wu×Wv的联合权值。
请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
题目链接：codevs http://www.cnblogs.com/smileandyxu/p/5348411.html
图论问题，70分暴力都很好打吧，只要枚举所有点dfs找到他的距离为二的点，维护一个tot和一个max就可以了，细节自己想想，代码
等下会贴出来，正解是乘法的结合律，这个题目可以转换一下，对于每个点对，可以看成由一点中间点中转而成，就是每个点对中必定有
且只隔一个点吧，因为图是棵树，只要枚举每个入度为1的点作为中转点，然后将其儿子与其他所有儿子相乘就可以了，但这是n平方的啊！会超时。
所以我们用乘法原理，统计所有儿子权值和，然后用权值和剪去自己的权值的值再乘自己的权值，这样就是O（n）完成了。
另外，推荐我的博客:http://www.cnblogs.com/renjianshige/
暴力代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<queue> #include<cstring> const int MAXN=200010; using namespace std; struct edge{ int first; int next; int to; int quan; }a[2*MAXN]; bool b[MAXN]; struct node{ int now; int fa; node(){} node(int _now,int _fa):now(_now),fa(_fa){} }; int dian[MAXN]; int in[MAXN]; int n,num=0; void addedge(int from,int to){ a[++num].to=to; a[num].quan=1; a[num].next=a[from].first; a[from].first=num; } long long tott=0,big=0; void dfs(int now,int fa,int time){ for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to; if(to==fa) continue; if(time==2){ if(b[to]) continue; long long dianquan=dian[fa]*dian[to]; big=max(big,dianquan); tott=(tott+dianquan)%10007; continue; } dfs(to,now,time+1); } } int main(){ memset(dian,0,sizeof(dian)); memset(b,0,sizeof(b)); scanf("%d",&n); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } for(int i=1;i<=n;i++){ scanf("%d",&dian[i]); } for(int i=1;i<=n;i++){ dfs(i,0,1); b[i]=1; } printf("%lld %lld ",big,(tott*2)%10007); return 0; }
AC代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<queue> #include<cstring> const int MAXN=200010; using namespace std; struct edge{ int first; int next; int to; int quan; }a[2*MAXN]; bool b[MAXN]; int dian[MAXN]; int in[MAXN]; int n,num=0; void addedge(int from,int to){ a[++num].to=to; a[num].quan=1; a[num].next=a[from].first; a[from].first=num; } long long tott=0,big=0; void dfs(int now){ long long tot=0,big1=0,big2=0; for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to; tot=(tot+dian[to])%10007; if(dian[to]>big1) { big1=dian[to]; continue; } if(dian[to]<=big1&&dian[to]>big2) big2=dian[to]; } for(int i=a[now].first;i;i=a[i].next){ tott+=dian[a[i].to]*(tot-dian[a[i].to])%10007; if(tott<0) tott+=10007; tott=tott%10007; } if(big<big1*big2) big=big1*big2; } int main(){ memset(dian,0,sizeof(dian)); memset(b,0,sizeof(b)); scanf("%d",&n); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); in[x]++; in[y]++; } for(int i=1;i<=n;i++){ scanf("%d",&dian[i]); } for(int i=1;i<=n;i++){ if(in[i]==1) continue; dfs(i); } printf("%lld %lld ",big,tott%10007); return 0; }