Luogu联合权值

2017-08-05

联合权值

思路

挺有意思的呐….

距离要求为2这个信息很有趣，我们可以枚举中间点，然后再枚举这个中间点所连的点—这些点两两之间一定是距离为二的，而且由于中间点不同，枚举到的所有点对也一定是不重复的

然后求最大值，我们可以枚举的时候顺带统计一个[到当前点为止之前的最大权值是多少]，然后用这个max与这次枚举到的点相乘，最大值一定属于其中—记得更新max

再来就是求sum，我们假设点A连接着点B、C、D、E，那么B可以与C、D、E拼成对，sum要+=BC、BD、BE—也就是除了B自己以外，A所连的所有点

那么就可以在求max时顺带求出一个sum[i]，表示i所连得所有点的权值和，这样对于i，枚举他的孩子，对ans-sum的贡献就是w[son]*(sum[i]-w[son])

代码

#define ll long long
#define mod 10007ll
#include<iostream>
#define N 500010
#include<cstdio>
using namespace std;
ll sum[N],e,ams,ans,n;
ll head[N],to[N],next[N],w[N];
void buid(ll u,ll v)
{
	next[++e]=head[u],head[u]=e;
	to[e]=v;
}
void xfs()
{
	for(int now=1;now<=n;++now)
	{
		ll itmax=0;
		for(int i=head[now];i;i=next[i])
		{
			int j=to[i];
			sum[now]+=w[j];
			ams=max(ams,itmax*w[j]);
			itmax=max(itmax,w[j]);
		}
	}
}
void Yeah_RPG()
{
	for(int now=1;now<=n;++now)
	{
		for(int i=head[now];i;i=next[i])
		{
			int j=to[i];
			ans+=(sum[now]-w[j])*w[j];
			ans%=mod;
		}
	}
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<n;++i)
	{
		ll u,v;
		scanf("%lld%lld",&u,&v);
		buid(u,v);
		buid(v,u);
	}
	for(int i=1;i<=n;++i) scanf("%lld",&w[i]);
	xfs();
	Yeah_RPG();
	printf("%lld %lld",ams,ans);
	return 0;
}
Comment Box
(update the code to your comment plugin in comment-full.html)