记录编号	449460	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	0.332 s
提交时间	2017-09-14 14:43:54	内存使用	8.71 MiB

#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

const long long MOD=10007;
long long n,mx1[200010],mx2[200010],sum[200010],w[200010],ans1=-1e9,ans2=0;
vector<int>e[200010];

void dfs(int cur,int fa)
{
	for(int i=0;i<e[cur].size();i++){
		sum[cur]+=w[e[cur][i]];
		sum[cur]%=MOD;
		if(mx1[cur]<=w[e[cur][i]]){
			mx2[cur]=mx1[cur];
			mx1[cur]=w[e[cur][i]];
		}
		else{
			mx2[cur]=max(mx2[cur],w[e[cur][i]]);
		}
	}
	if(e[cur].size()>=2) ans1=max(ans1,mx1[cur]*mx2[cur]);
	for(int i=0;i<e[cur].size();i++){
		ans2+=(w[e[cur][i]]*(((sum[cur]-w[e[cur][i]]))+MOD)%MOD);
		ans2%=MOD;
	}
	for(int i=0;i<e[cur].size();i++){
		if(e[cur][i]==fa) continue;
		dfs(e[cur][i],cur);
	}
	return;
}

int main()
{
	freopen("linkb.in","r",stdin);
	freopen("linkb.out","w",stdout);
	scanf("%lld",&n);	
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%lld%lld",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
	dfs(1,0);
	printf("%lld %lld",ans1,ans2%MOD);
	return 0;
}