记录编号	152226	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.300 s
提交时间	2015-03-13 20:40:41	内存使用	4.13 MiB

#include <fstream>
#include <vector>
using namespace std;
ifstream in("linkb.in");
ofstream out("linkb.out");
long long n,w[200001]={0},best=0,ans=0;
vector<int>f[200001];
int mark(int x)
{
	long long i,s=0,y=0,k=0,be=0,c=0,re=0;
	for(i=0;i<f[x].size();i++)
	{
		int v=f[x][i];
		s+=w[v];y+=w[v]*w[v];
		if(w[v]>be)
		{
			be=w[v];
			re=v;
		}
	}
	for(i=0;i<f[x].size();i++)
	{
		int v=f[x][i];
		if(w[v]!=be||re!=v)
		{
			if(w[v]>c)c=w[v];
		}
	}
	int ruo;
	ruo=be*c;
	if(ruo>best)best=ruo;
	k=s*s-y;
	ans+=k;
	return 0;
}
int main()
{
	int i,x1,x2;
	in>>n;
	for(i=1;i<=n-1;i++)
	{
		in>>x1>>x2;
		f[x1].push_back(x2);
		f[x2].push_back(x1);
	}
	for(i=1;i<=n;i++)in>>w[i];
	//for(i=1;i<=n;i++)out<<w[i]<<endl;
	for(i=1;i<=n;i++)mark(i);
	out<<best<<' '<<ans%10007<<endl;
	return 0;
}