[NOIP2014提高组]联合权值

题目：洛谷P1351、Vijos P1906、codevs3728、UOJ#16。

题目大意：有一个无向连通图，有n个点n-1条边，每个点有一个权值$W_i$，每条边长度为1。规定两个距离为2的点i和j可以产生$W_i×W_j$的联合权值。求最大的联合权值是多少，联合权值之和是多少。

解题思路：首先，距离为2的点只有两种情况：①点u和它父亲的父亲；②点u和它的兄弟。那么我们只需遍历全图，记录该点父亲的父亲即可。对于每个节点，求出它所有儿子和儿子之间的联合权值是多少，加起来即可。

这样子可能会超时。那么我们可以用一个变量记录前面儿子的权值和，然后直接乘这个和即可。最后答案乘2。

对于第一问，我们也思考以上两种情况。第①种很好考虑，第②种我们只需记录最大权值和次大权值，然后相乘就是可能的最大值了。

于是就过了。

C++ Code：

#include<cstdio>

#include<vector>

using namespace std;

vector<int>G[200002];

int n,d[200002],ans=0,Max=0;

bool b[200002]={0};

void addedge(int from,int to){

	G[from].push_back(to);

	G[to].push_back(from);

}

void dfs(int u,int fa,int fasfa){

	b[u]=true;

	if(fasfa)ans=(ans+d[u]*d[fasfa]%10007)%10007;

	int sum=0,no1=0,no2=0;

	for(int i=0;i<G[u].size();++i)

	if(!b[G[u][i]]){

		if(d[G[u][i]]>no1)no2=no1,no1=d[G[u][i]];else

		if(d[G[u][i]]>no2)no2=d[G[u][i]];

		ans=(ans+d[G[u][i]]*sum%10007)%10007;

		sum=(sum+d[G[u][i]])%10007;

	}

	if(no1*no2>Max)Max=no1*no2;

	if(d[u]*d[fasfa]>Max)Max=d[u]*d[fasfa];

	for(int i=0;i<G[u].size();++i)

	if(!b[G[u][i]]){

		b[G[u][i]]=true;

		dfs(G[u][i],u,fa);

	}

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<n;++i){

		int x,y;

		scanf("%d%d",&x,&y);

		addedge(x,y);

	}

	for(int i=1;i<=n;++i)scanf("%d",&d[i]);

	dfs(1,0,0);

	printf("%d %d\n",Max,ans*2%10007);

	return 0;

}

巴特西

[NOIP2014提高组]联合权值

最新文章

热门文章