联合权值
程序员文章站
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;
}
上一篇: 邻接表——数组实现
下一篇: hdu5521 Meeting