noip2014 洛谷1351 联合权值

xiaoxiao2021-02-28  29

题目:联合权值

思路:

首先n个点n-1条边的联通图是一颗无根树。

对于每两个距离为2的点,可以知道,它们一定和一个公共点有连边。

枚举公共点i,再用O(n)的时间算出与这个点相连的点中权值最大的两个点,求出联合权值。最后求出这些联合权值的最大值。

所有联合权值的和,就可以利用乘法分配律的思想。假设每一个和点i有关的联合权值的值为 x*i+y*i+z*i ,那么这个值也就是(x+y+z)*i,所以就可以利用一些小技巧处理x+y+z,就能在O(n^2)的时间内求出了。

注意:

1、最大的两个值的求法不能写错,当当前值在最大的两个值之间时,不能忘记更新次大值。

2、题中只说了和要取模,最大值不能取模。

代码:

#include<bits/stdc++.h> using namespace std; #define maxn 200000 #define ll long long #define md 10007 int n; int w[maxn+5]; vector<int> a[maxn+5]; ll ans=0,sum=0; int main() { scanf("%d",&n); for(int i=1; i<n; i++) { int x,y; scanf("%d%d",&x,&y); a[x].push_back(y),a[y].push_back(x); } for(int i=1; i<=n; i++) { scanf("%d",&w[i]); } for(int i=1;i<=n;i++){ ll max1=0,max2=0; ll cnt=0; for(int j=0;j<a[i].size();j++){ if(w[a[i][j]]>max1){ max2=max1; max1=w[a[i][j]]; } else if(w[a[i][j]]>max2) { //注意不能写掉 max2=w[a[i][j]]; } sum=(sum+cnt*w[a[i][j]])%md; cnt=(cnt+w[a[i][j]])%md; } ans=max(ans,max1*max2); } printf("%lld %lld",ans,(sum*2)%md); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1450122.html

最新回复(0)