记录编号	291929	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.241 s
提交时间	2016-08-08 13:49:38	内存使用	7.81 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
struct edge{
	int to,prev;
	edge():prev(0){}
}e[maxn<<1];
void insert(int,int);
void bfs();
void rebfs();
int len=0,last[maxn]={0};
int n,w[maxn],sum[maxn],mxa[maxn],mxb[maxn],prt[maxn],ans=0,mx=0,x,y;
int a[maxn],head=1,tail=1;//a既是模拟队列也是bfs序
int main(){
	freopen("linkb.in","r",stdin);
	freopen("linkb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	bfs();
	//printf("\n");
	rebfs();
	printf("%d %d",mx,(ans<<1)%10007);
	//printf("\n");
	//for(int i=1;i<=n;i++)printf("i=%d w=%d sum=%d mxa=%d mxb=%d\n",i,w[i],sum[i],mxa[i],mxb[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void insert(int x,int y){
	e[++len].to=y;
	e[len].prev=last[x];
	last[x]=len;
}
void bfs(){
	int x,y;
	a[tail++]=1;
	while(head!=tail){
		x=a[head++];
		//printf("%d ",x);
		for(int i=last[x];i;i=e[i].prev){
			y=e[i].to;
			if(y==prt[x])continue;
			prt[y]=x;
			if(w[y]>mxa[x]){
				mxb[x]=mxa[x];
				mxa[x]=w[y];
			}
			else if(w[y]>mxb[x])mxb[x]=w[y];
			a[tail++]=y;
		}
	}
}
void rebfs(){
	int x;
	for(int i=n;i;i--){
		x=a[i];
		//printf("\nx=%d\n",x);
		ans+=sum[prt[x]]*w[x];
		ans%=10007;
		//printf("(bro)ans+=sum[%d](now%d)*w[%d](%d)=%d\n",prt[x],sum[prt[x]],x,w[x],sum[prt[x]]*w[x]);
		sum[prt[x]]+=w[x];
		sum[prt[x]]%=10007;
		ans+=sum[x]*w[prt[x]];
		ans%=10007;
		//printf("(prt)ans+=sum[%d](now%d)*w[%d](%d)=%d\n",x,sum[x],prt[x],w[prt[x]],sum[x]*w[prt[x]]);
		mx=max(mx,mxa[x]*mxb[x]);
		mx=max(mx,mxa[x]*w[prt[x]]);
	}
}
/*
5
1 2
2 3
3 4
4 5
1 5 2 3 10
Answer:
20 74
*/
/*
9
3 8
1 4
2 1
9 3
2 3
4 5
4 6
4 7
10 3 9 8 1 4 3 7 2
Answer:
90 508
*/
/*
解法：
不要被这个题吓到，暴力枚举是很费的。
与一个点距离为2只有三种情况：
1.它的父亲的父亲
2.它的儿子的儿子
3.它的兄弟
其中前两种情况只需求出一种即可(另一种会被这一种包括)。
为每个节点记录一个附加信息sum表示儿子的权和，
这样2就直接用它的权值乘上儿子的权和即可，
3利用sum也可以做到O(son)计算。
总时间复杂度应该是O(n)。
为了避免爆栈，这里采用bfs逆序处理(这样一定可以保证处理顺序是深度严格递减的)。
顺便一提并没有用到树剖和LCA什么的鬼东西。
至于求最大值，直接记录儿子中的最大权和次大权，比较最大权*父亲和最大权*次大权即可。
*/