NOIP2014 联合权值

题目

vijos1906

luogu1351

代码

ps.本来看到n-1条边第一反应就是建树，奈何水平太差一直T，最终只得感叹：“暴力出奇迹”

代码

#include <cstdio>
#include <iostream>
#define N 400005
#define mod 10007
#define ll long long
using namespace std;

int n,w[N];
int num,to[N],nt[N],p[N];
void add(int u,int v){to[++num]=v;nt[num]=p[u];p[u]=num;}
ll ans;int Max;
void deal(int x)
{
	ll sum=0;int m1=0,m2=0;
	for(int e=p[x];e;e=nt[e])//从某点出发能搜到的任意两点距离为2 
	{
		int k=to[e];
		if(w[k]>m1) m2=m1,m1=w[k];
		else if(w[k]>m2) m2=w[k];//这里若用max维护m1,m2的大小关系会超时 
		ans+=w[k]*sum;//sum记录已经都过点的权值和，避免(u,v),(v,u)的重复计算，输出时ans*2即可 
		sum+=w[k];
	}
	Max=max(Max,m1*m2);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	for(int i=1;i<=n;i++) deal(i);
	printf("%d %lld",Max,ans*2%mod);
	return 0;
}