记录编号	472117	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.708 s
提交时间	2017-11-07 11:31:52	内存使用	70.09 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 201000
const int mod=10007;
int n;
struct haha{
	int next,to;
}edge[N*2];
int head[N],cnt=1;
void add(int u,int v){
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
struct xixi{
	int lc,rc,sum,ma;
}tree[N*20];
int root[N],size;
int dfsl[N],dfsr[N],ji,dep[N],w[N],fa[N];
void dfs(int x){
	dfsl[x]=++ji;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to!=fa[x]){
			dep[to]=dep[x]+1;
			fa[to]=x;
			dfs(to);
		}
	}
	dfsr[x]=ji;
}
void update(int pos,int num,int &rt,int l,int r){
	if(!rt) rt=++size;
	if(l==r){
		tree[rt].sum=tree[rt].ma=num;return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) update(pos,num,tree[rt].lc,l,mid);
	else update(pos,num,tree[rt].rc,mid+1,r);
	tree[rt].sum=(tree[tree[rt].lc].sum+tree[tree[rt].rc].sum)%mod;
	tree[rt].ma=max(tree[tree[rt].lc].ma,tree[tree[rt].rc].ma);
}
int ans(0),maxans(0);
xixi query(int xl,int xr,int &rt,int l,int r){
	xixi res;res.ma=res.sum=0;
	if(!rt) return res;
	if(l>=xl&&r<=xr){
		return tree[rt];
	}
	int mid=(l+r)>>1;
	if(xl<=mid)	res=query(xl,xr,tree[rt].lc,l,mid);
	if(xr>mid){
		xixi temp=query(xl,xr,tree[rt].rc,mid+1,r);
		res.ma=max(res.ma,temp.ma);res.sum=(res.sum+temp.sum)%mod;
	}
	return res;
}
int main(){
	freopen("linkb.in","r",stdin);
	freopen("linkb.out","w",stdout);
	scanf("%d",&n);
	pos(i,1,n-1){
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	pos(i,1,n) scanf("%d",&w[i]);
	dfs(1);
	pos(i,1,n){
		update(dfsl[i],w[i],root[dep[i]],1,n);
	}
	pos(i,1,n){
		xixi temp=query(dfsl[i],dfsr[i],root[dep[i]+2],1,n);
		ans=(ans+w[i]*temp.sum)%mod;maxans=max(maxans,w[i]*temp.ma);
		if(dfsl[fa[i]]+1<=dfsl[i]-1){
			temp=query(dfsl[fa[i]]+1,dfsl[i]-1,root[dep[i]],1,n);
			ans=(ans+w[i]*temp.sum)%mod;maxans=max(maxans,w[i]*temp.ma);
		}
	}
	cout<<maxans<<" "<<(ans*2)%mod;
	return 0;
}