记录编号	200937	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.353 s
提交时间	2015-10-29 18:56:45	内存使用	5.65 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define MOD 10007ll
#define LL long long
using namespace std;
vector<int> map[200005];
int N;
LL W[200005];
LL sum=0;
LL MAXN=0;
LL ceng[200005];
inline void open()
{
	freopen("linkb.in","r",stdin);
	freopen("linkb.out","w",stdout);
}
inline void dfs(int v,int pre,int prepre)
{
	int next;vector<LL> ff;
	if(W[v]*W[prepre]>MAXN)
	{
		MAXN=W[v]*W[prepre];
	}
	sum+=W[v]*W[prepre];sum%=MOD;
	for(int i=0;i<map[v].size();i++)
	{
		next=map[v][i];
		if(pre!=next)
		{
			ff.push_back(W[next]);
			sum+=ceng[v]*W[next];sum%=MOD;
			ceng[v]+=W[next];
			ceng[v]%=MOD;
			dfs(next,v,pre);
		}
	}
	sort(ff.begin(),ff.end());
	int siz=ff.size();
	if(siz>1)
		MAXN=max(MAXN,ff[siz-1]*ff[siz-2]);
}
int main()
{
	open();
	int a,b;
	scanf("%d",&N);
	for(int i=1;i<=N-1;i++)
	{
		scanf("%d%d",&a,&b);
		map[a].push_back(b);
		map[b].push_back(a);
	}
	for(int i=1;i<=N;i++)
		scanf("%lld",&W[i]);
	dfs(1,N+1,N+2);
	sum*=2;
	sum%=MOD;
	printf("%lld %lld\n",MAXN,sum);
	return 0;
}