[NOIP2014]联合权值

这题在Vijos上难度8哈铪紦奤妎虾蝦鉿蛤

题目(vijos)
这题一开始稍微想复杂了……
其实思考一下就明白,距离为2的两个点之间一定有一个点(废话),
于是我们反过来想:连接在一个点上的不同的两个点一定距离为2。
所以,这题可以这样:
枚举每一个点,把连接在这个点上的点的权值用一个d数组记录下来。
然后对d数组从大到小排序,这样第一题就解决了:ans1=max(ans1,d[1]*d[2])。
第二问采用前缀和的方式解决:
比如连接在同一个点上的点的权值分别为1,3,5,6,
假设我们不考虑有序数对,那么总和为1*(3+5+6)+3*(5+6)+5*6,
明显可以用前缀和来优化。
答案为sum*2。
这题就解决了~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
template <class ___E> inline void read(___E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck) e = -e;
}
const int mod=10007;
struct edge{
	int vk;
	int next;
}e[400005];
int a[200005];
int d[200005];
int sum;
int maxn;
ll s[200005];
int n,m;
int head[200005],t=1;
bool cmp(const int &x,const int &y)
{
	return x>y;
}
void ad(int u,int v)
{
	e[t].vk=v;
	e[t].next=head[u];
	head[u]=t++;
}
int main()
{
	read(n);
	for (register int i=1;i<n;++i)
	{
		int x,y;
		read(x);
		read(y);
		ad(x,y);
		ad(y,x);
	}
	for (register int i=1;i<=n;++i)
	{
		read(a[i]);
	}
	int cnt=0;
	for (register int k=1;k<=n;++k)
	{
		for (int i=1;i<=cnt;++i)
		{
			d[i]=0;
			s[i]=0;
		}
		cnt=0;
		for (int i=head[k];i;i=e[i].next)
		{
			++cnt;
			int v=e[i].vk;
			d[cnt]=a[v];
		}
		if (cnt==1) continue;
		sort(d+1,d+cnt+1,cmp);
		maxn=max(maxn,d[1]*d[2]);
		for (int i=1;i<=cnt;++i)
			s[i]=s[i-1]+d[i];
		for (int i=1;i<cnt;++i)
		{
			sum=sum+(((d[i]%mod)*((s[cnt]-s[i])%mod))%mod);
			sum%=mod;
		}
	}
	printf("%d %d",maxn,(sum*2)%mod);
	return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注