记录编号	538055	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.179 s
提交时间	2019-07-21 11:06:04	内存使用	9.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 300010
using namespace std;
struct Edge{
	int next,to;
}e[maxn<<1];int len,head[maxn<<1];
int N,v[maxn],sum,Max,ufs[maxn],du[maxn],ans,Mod=10007;
bool flag[maxn];
void _addedge(int x,int y){
	len++;e[len].to=y;e[len].next=head[x];head[x]=len;
}
void _dfs(int x){
	flag[x]=1;int sum=0,Max1=0,Max2=0;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(ufs[x]==y)continue;
		ufs[y]=x;ans+=v[y]*sum;ans=ans%Mod;sum+=v[y];sum=sum%Mod;
		if(v[y]>Max1){
			Max2=Max1;Max1=v[y];
		}
		else if(v[y]>Max2)Max2=v[y];
		Max=max(Max,Max1*Max2);
		_dfs(y);
	}
	Max=max(Max,Max1*v[ufs[x]]);
	ans+=sum*v[ufs[x]];ans=ans%Mod;
}
int Main();
int haha=Main();
int main(){;}
int Main(){
	freopen("linkb.in","r",stdin);freopen("linkb.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<N;i++){
		int x,y;scanf("%d%d",&x,&y);_addedge(x,y);_addedge(y,x);du[x]++;du[y]++;
	}
	for(int i=1;i<=N;i++)scanf("%d",&v[i]);
	for(int i=1;i<=N;i++){
		if(du[i]<2&&!flag[i])_dfs(i);
	}
	ans=ans*2;ans=ans%Mod; 
	printf("%d %d",Max,ans);
	return 0;
}