记录编号	139875	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.975 s
提交时间	2014-11-17 14:31:46	内存使用	12.12 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=200010,MOD=10007;
int N;
vector<int> c[SIZEN];
vector<int> son[SIZEN];
int W[SIZEN];
int fa[SIZEN]={0};
vector<int> Blis;
class PAIR{
public:
	int mx;
	int s;
	void print(void){
		cout<<"("<<mx<<" "<<s<<")";
	}
	void clear(void){
		mx=s=0;
	}
	PAIR(void){
		mx=s=0;
	}
};
PAIR mkpr(int x,int y){
	PAIR a;
	a.mx=x,a.s=y;
	return a;
}
PAIR operator + (PAIR a,PAIR b){
	PAIR c;
	c.mx=max(a.mx,b.mx);
	c.s=(a.s+b.s)%MOD;
	return c;
}
PAIR P[SIZEN];
PAIR sp[SIZEN];
void update_1(int x){//子之子
	for(int i=0;i<son[x].size();i++){
		int u=son[x][i];
		P[x]=P[x]+sp[u];
		sp[x]=sp[x]+mkpr(W[u],W[u]);
	}
}
PAIR pre[SIZEN],suf[SIZEN];
void update_2(int x){//x兄弟之间
	if(son[x].size()<=1) return;
	int u=son[x].front();
	pre[0]=mkpr(W[u],W[u]);
	for(int i=1;i<son[x].size();i++){
		u=son[x][i];
		pre[i]=pre[i-1]+mkpr(W[u],W[u]);
		P[u]=P[u]+pre[i-1];
	}
	u=son[x].back();
	suf[son[x].size()-1]=mkpr(W[u],W[u]);
	for(int i=son[x].size()-2;i>=0;i--){
		u=son[x][i];
		suf[i]=suf[i+1]+mkpr(W[u],W[u]);
		P[u]=P[u]+suf[i+1];
	}
}
queue<int> Q;
bool vis[SIZEN]={0};
int f[SIZEN];
void BFS(int S){
	memset(fa,0,sizeof(fa));
	memset(vis,0,sizeof(vis));
	while(!Q.empty()) Q.pop();
	for(int i=1;i<=N;i++) son[i].clear();
	Blis.clear();
	vis[S]=true;Q.push(S);f[S]=0;
	while(!Q.empty()){
		int x=Q.front();Q.pop();Blis.push_back(x);
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i];
			if(u==fa[x]) continue;
			fa[u]=x;
			son[x].push_back(u);
			f[u]=f[x]+1;
			Q.push(u);
		}
	}
}
void work_big(void){
	BFS(1);
	for(int i=1;i<=N;i++){//父之父
		if(fa[fa[i]]!=0){
			int u=fa[fa[i]];
			P[i]=P[i]+mkpr(W[u],W[u]);
		}
	}
	for(int i=Blis.size()-1;i>=0;i--) update_1(Blis[i]);//子之子
	for(int i=0;i<Blis.size();i++) update_2(Blis[i]);//兄弟
	int mx=0,sum=0;
	for(int i=1;i<=N;i++){
		mx=max(mx,W[i]*P[i].mx);
		sum+=(W[i]*P[i].s)%MOD;
		sum%=MOD;
	}
	printf("%d %d\n",mx,sum);
}
void work_small(void){//其实这个傻叉了
	int mxw=0,wsum=0;
	for(int i=1;i<=N;i++){
		BFS(i);
		for(int j=1;j<=N;j++){
			if(f[j]==2){
				int now=W[i]*W[j];
				mxw=max(mxw,now);
				wsum+=now;
				wsum%=MOD;
			}
		}
	}
	printf("%d %d\n",mxw,wsum);
}
void read(void){
	scanf("%d",&N);
	int a,b;
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
	for(int i=1;i<=N;i++) scanf("%d",&W[i]);
}
int main(){
	freopen("linkb.in","r",stdin);
	freopen("linkb.out","w",stdout);
	read();
	work_big();
	return 0;
}