记录编号	139495	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.197 s
提交时间	2014-11-12 16:19:43	内存使用	4.13 MiB

/*========================================================*/
/*======================BY ASM.DEF========================*/
/*========================================================*/
#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("linkb.in", "r");
FILE *out = fopen("linkb.out", "w");
#endif
#define pb push_back
#define iter(v) v::iterator
template<typename T> inline bool getd(T &x){
	int c = fgetc(in);
	bool minus = 0;
	while(c != '-' && c != EOF && !isdigit(c))c = fgetc(in);
	if(c == EOF)return 0;
	if(c == '-'){
		minus = 1;
		x = 0;
	}
	else x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 + c - '0';
	if(minus)x = -x;
	return 1;
}
using namespace std;
/*==========================================================*/
const int maxn = 200000 + 5, mod = 10007;
int n, W[maxn], pre[maxn] = {0}, Max = 0, Sum = 0;
vector<int> adj[maxn];

inline bool cmp(int a, int b){return W[a] > W[b];}

inline void calc(int cur){
	iter(vector<int>) it;
	int pow2S = 0, wS = 0;//平方和,权值和(\sum_{i=1}^{N}(a_i (\sum_{j=1}^N}a_j - a_i)) = wS^2 - pow2S)
	int firmax = 0, secmax = 0;
	for(it = adj[cur].begin();it != adj[cur].end();++it){
		pow2S = (pow2S + W[*it] * W[*it]) % mod;
		wS = (wS + W[*it]) % mod;
		if(W[*it] > firmax)secmax = firmax, firmax = W[*it];
		else if(W[*it] > secmax)secmax = W[*it];
	}
	Max = max(Max, firmax * secmax);
	Sum = (Sum + wS * wS) % mod;
	Sum = (Sum + mod - pow2S) % mod;
}

inline void work(){
	int i, u, v;
	getd(n);
	for(i = 1;i < n;++i){
		getd(u), getd(v);
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(i = 1;i <= n;++i)getd(W[i]);
	for(i = 1;i <= n;++i)
		calc(i);
	fprintf(out, "%d %d\n", Max, Sum);
}

int main(){
	
	work();
	
	#if defined DEBUG
	cout << endl << (double)clock() / CLOCKS_PER_SEC << " sec" << endl;
	#endif
	return 0;
}