首页 > 代码库 > [NOIP2014]联合权值 题解
[NOIP2014]联合权值 题解
题目大意：
有一棵树，求距离为2的点权的乘积的和以及最大值。
思路：
枚举每一个点，则与其相邻的点互为距离为2的点。该部分的最大值为点权最大的两个点的积，和为点的权值和的平方减去每个点的平方，这样每条边都被跑了两次，所以复杂度为O(n)。
用邻接表存储要开双倍数组（无向），当然像cyk大神一样直接跑边就不用考虑这个了。
代码：
邻接表：
1 #include<cstdio> 2 const int mo=10007,M=200008; 3 int cnt,x,y,n,i,ans,tot,w[M],v[M<<1],last[M<<1],head[M<<1]; 4 5 void add(int x,int y) { v[++cnt]=y,last[cnt]=head[x],head[x]=cnt; } 6 7 int main() 8 { 9 scanf("%d",&n); 10 for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x); 11 for (i=1;i<=n;i++) scanf("%d",&w[i]); 12 for (i=1;i<=n;i++) 13 { 14 int sum=0,max1=0,max2=0,j,o; 15 for (j=head[i];j;j=last[j]) 16 { 17 o=w[v[j]]; 18 sum=(sum+o)%mo; 19 if (o>max1) max2=max1,max1=o; 20 else if (o>max2) max2=o; 21 tot=(tot-o*o)%mo; 22 } 23 tot=(tot+sum*sum)%mo; 24 sum=max1*max2; 25 if (sum>ans) ans=sum; 26 } 27 printf("%d %d\n",ans,tot); 28 return 0; 29 }
%%%cyk大神：
1 #include<iostream> 2 using namespace std; 3 int i,n,maxx,ans,x[200005],y[200005],w[200005]; 4 int am[200005],am2[200005],s[200005],qs[200005]; 5 int main() 6 { 7 cin>>n; 8 for (i=1;i<=n-1;i++) cin>>x[i]>>y[i]; 9 for (i=1;i<=n;i++) cin>>w[i]; 10 for (i=1;i<=n-1;i++) 11 { 12 s[x[i]]=(s[x[i]]+w[y[i]])%10007; 13 qs[x[i]]=(qs[x[i]]+w[y[i]]*w[y[i]])%10007; 14 s[y[i]]=(s[y[i]]+w[x[i]])%10007; 15 qs[y[i]]=(qs[y[i]]+w[x[i]]*w[x[i]])%10007; 16 if (w[y[i]]>am[x[i]]) {am2[x[i]]=am[x[i]];am[x[i]]=w[y[i]];} 17 else if (w[y[i]]>am2[x[i]]) am2[x[i]]=w[y[i]]; 18 if (w[x[i]]>am[y[i]]) {am2[y[i]]=am[y[i]];am[y[i]]=w[x[i]];} 19 else if (w[x[i]]>am2[y[i]]) am2[y[i]]=w[x[i]]; 20 } 21 maxx=0; 22 for (i=1;i<=n;i++) maxx=max(maxx,am[i]*am2[i]); 23 ans=0; 24 for (i=1;i<=n;i++) ans=(ans+s[i]*s[i]-qs[i])%10007; 25 cout<<maxx<<‘ ‘<<ans; 26 }
[NOIP2014]联合权值 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。