欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

联合权值

程序员文章站 2022-05-22 14:34:26
...

题目传送门sxazr
本题可直接枚举每个点,然后枚举与它相连的两个点,这两个点的乘积便是一个联合权值;
可以记录下每个点与它相连的点的最大值和次大值,结果就是取最大值和次大值乘积的最大;
求和的话,可以记录下一个点相连所有点的和s[i],sum=∑(w[j]*(s[i]-w[j])) (j是与i相连的点)枚举每个点的sum,
ans=∑sum;
代码比较简陋,啰嗦,比较容易理解哈。

#include <iostream>
#include <cstdio>
using namespace std;
const int N=200001;
int n,hed[N],net[N<<1],to[N<<1],w[N],g,ma1[N],ma2[N],k[N],maxx;
long long s[N],ans,MOD=10007;
void add(int x,int y)
{
	net[++g]=hed[x];hed[x]=g;to[g]=y;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);k[u]++;k[v]++;  //k[i]表示与i相连的点的个数
	}
	for(int i=1;i<=n;i++)
	  scanf("%d",w+i);
	for(int i=1;i<=n;i++){
		for(int j=hed[i];j;j=net[j]){
			int v=w[to[j]];s[i]+=v;
			if(v>=ma1[i]) ma2[i]=ma1[i],ma1[i]=v;
			else if(v>ma2[i]&&v<=ma1[i]) ma2[i]=v;
		}
	}
	for(int i=1;i<=n;i++){
		if(k[i]==1) continue;
		if(ma1[i]*ma2[i]>maxx) maxx=ma1[i]*ma2[i];
	}
	for(int i=1;i<=n;i++){
		if(k[i]==1) continue;
		for(int j=hed[i];j;j=net[j]){
			ans=(ans+w[to[j]]*(s[i]-w[to[j]]))%MOD;
		}		  
	}
	cout<<maxx<<" "<<ans;
	return 0;
}