记录编号	292247	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2016-08-08 17:28:36	内存使用	4.30 MiB

#include <cstdio>
#include <cstring>
using namespace std;

int value[210000];
int Max[210000], sum[210000];
int from[210000], to[210000];
//max[i]: 与i相邻的权值最大的点的权值, sum[i]: 与i相邻的所有点的权值和 
const int mod = 10007;
int maxn, ans;

inline int GetMax(const int& a, const int& b)
{
	if(a > b)	return a;
	return b;
}

inline int Read()
{
	int a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')	ch = getchar();
	while(ch >= '0' && ch <='9'){
		a = a*10 + ch-'0';
		ch = getchar();
	}
	return a;
}

int main()
{
	freopen("linkb.in", "r", stdin); freopen("linkb.out", "w", stdout);
	int n = Read();
	for(int i = 1; i < n; i++)	from[i] = Read(), to[i] = Read();
	for(int i = 1; i <= n; i++)	value[i] = Read();
	for(int i = 1; i < n; i++){
//		printf("max[%d] %d\n", from[i], Max[from[i]]);
		maxn = GetMax(maxn, Max[from[i]]*value[to[i]]);
		Max[from[i]] = GetMax(Max[from[i]], value[to[i]]);
		maxn = GetMax(maxn, Max[to[i]]*value[from[i]]);
		Max[to[i]] = GetMax(Max[to[i]], value[from[i]]);
		sum[to[i]] += value[from[i]]; sum[to[i]] %= mod;
		sum[from[i]] += value[to[i]]; sum[from[i]] %= mod;
	}
	for(int i = 1; i < n; i++){
		ans += (sum[from[i]]-value[to[i]]) * value[to[i]];
		ans += (sum[to[i]]-value[from[i]]) * value[from[i]];
		ans %= mod;
	}
//	for(int i = 1; i <= n; i++)	printf("max[%d] %d\n", i, Max[i]);
	printf("%d %d", maxn, ans);
	fclose(stdin); fclose(stdout);
	return 0;
}
/*
5
1 2
2 3
3 4
4 5
1 5 2 3 10
*/
/*
7
1 2 
2 3
1 6
1 5
6 7
2 4
1 1 1 1 1 1 1
*/
/*
20
1 2
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 2
11 1
1 12
1 13
1 14
14 15
16 14
14 17
14 18
19 14
20 15
4 6 5 9 2 4 9 1 9 4 2 5 4 3 6 6 10 5 8 2

ans: 81 4390
*/