记录编号	467318	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	snake	是否通过	通过
代码语言	C++	运行时间	0.265 s
提交时间	2017-10-30 13:43:36	内存使用	3.37 MiB

//#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream cin("linkb.in");ofstream cout("linkb.out");

const int MAX=200010,p=10007;
vector<int> a[MAX];
int v[MAX];
int result=0,maxx=-1;

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int t1,t2;
		cin>>t1>>t2;
		a[t1].push_back(t2);
		a[t2].push_back(t1);
	}
	for(int i=1;i<=n;i++) cin>>v[i];
	for(int i=1;i<=n;i++)
	{
		int sumn=0,sump=0,max1=-1,max2=-1;	//max1 for est
		if(a[i].size()>=2)
		{
			for(int j=0;j<a[i].size();j++)
			{
				int temp=v[a[i][j]];
				if(temp>max1) {max2=max1;max1=temp;}
				else if(temp>max2) max2=temp;
				temp%=p;
				sumn+=temp;
				sumn%=p;
				temp*=temp;
				temp%=p;
				sump+=temp;
				sump%=p;
			}
			result+=(sumn*sumn-sump)%p;
			result%=p;
			if(max1*max2>maxx) maxx=max1*max2;
		}
	}
	cout<<maxx<<" "<<result;
	return 0;
}



/*
simple input:
5
1 2
2 3
3 4
4 5
1 5 2 3 10

simple output:
20 74

*/