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

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#define MOD (10007)
using namespace std;

int w[200002];
long long r = 0;
long long m = -1;

class node
{
public:	
	vector<int>adj;
	int v;
	void add_way_to(int o)
	{
	//	v = 0;
		this->adj.push_back(o);
	}
};

node ns[200002];

int main()
{
	freopen("linkb.in", "r", stdin);
	freopen("linkb.out", "w", stdout);
	int n;
	int i,j,k;
	int u,v;
	int p,q;
	long long s;
	
	scanf("%d", &n);
	for(i = 1; i <= n-1; i++)
	{
		scanf("%d %d", &u, &v);
		ns[u].add_way_to(v);
		ns[v].add_way_to(u);
	}
	for(i = 1; i <= n; i++)
	{
		cin >> v;
		ns[i].v= v;
	}
	vector<int>ll;
	for(i = 1; i <= n; i++) //枚举所有节点 
	{
		s = 0;
		ll.clear();
		if(ns[i].adj.size() == 1)continue;
		for(p = 0; p < ns[i].adj.size(); p++) //枚举当前节点的后继 
		{
			q = ns[i].adj[p];
		
			s += ns[q].v;
			ll.push_back(ns[q].v);
		}	
		sort(ll.begin(), ll.end());
		k = ll.size();
		u = s;
		for(p = 0; p < ns[i].adj.size(); p++)
		{
			s = u;
			q = ns[i].adj[p];
			s -= ns[q].v;
			s *= ns[q].v;
			r += s%MOD;
			r %= MOD;
			if(k > 1)
			{
				m = max(m, (long long)ll[k-1]*ll[k-2]);
			}
		}
	}
	cout << m << ' ' << r << endl;
	return 0;
}
	//s = 0;
			//for(u = 0; u < ns[q].adj.size(); u++) //枚举当前节点的后继的后继 
			//{
			//	v = ns[q].adj[u];
			//	if(v == i)continue;    //但是如果当前节点的后继的后继就是当前节点的话。。。
			//	if(v < i)continue;     //但是如果之前这两个节点已经计算过了。。。 
			//		s += ns[v].v;
			//	m = max(m,ns[i].v*ns[v].v);
			//}
			//r += ns[i].v * s;
			//r %= MOD;