记录编号	346820	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	zhjian	是否通过	通过
代码语言	C++	运行时间	0.865 s
提交时间	2016-11-12 15:57:23	内存使用	29.12 MiB

#include<bits/stdc++.h>

#define LL unsigned long long
#define BEGIN freopen("linkb.in","r",stdin);freopen("linkb.out","w",stdout);
#define END fclose(stdin);fclose(stdout);
#define SPEED std::ios::sync_with_stdio(false);

using namespace std;

const int N=1200005,M=10007;

int n,m;
int head[N],tot;
int ff[N][2];
int sum,ant;

struct node{
	int to,next;
}e[N];

struct point{
	int w;
	int h;
}p[N];

void add(int a,int b){
	e[tot].to=b;
	e[tot].next=head[a];
	head[a]=tot++;
}

void Add(int a,int b){
	add(a,b);
	add(b,a);
}

int cmp(point a,point b){
	return a.w<b.w;
}

int main(){
	BEGIN
 	SPEED
	cin>>n;
	memset(head,-1,sizeof(head));
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		Add(a,b);
	}
	for(int i=1;i<=n;i++){
		cin>>p[i].w;
		p[i].h=i;
	}
	for(int i=1;i<=n;i++){
		int ant1=0,ant2=0;
		ff[i][0]=ff[i][1]=0;
		for(int j=head[i];j!=-1;j=e[j].next){
			int t=p[e[j].to].w;
			ant1+=t;
			ant2+=t*t;
			if(ff[i][0]<t)
				swap(ff[i][0],t);
			ff[i][1]=max(ff[i][1],t);
			ant1%=M;
			ant2%=M;
		}
		ant=max(ant,ff[i][0]*ff[i][1]);
		int t=(ant1*ant1)-ant2;
		t=(t+10*M)%M;
		sum+=t;
		sum%=M;
	}
	cout<<ant<<" "<<sum<<endl;
	END
	return 0;
}