#16. 【NOIP2014】联合权值

描述

无向连通图

G

有

n

个点，

n - 1

条边。点从

1

到

n

依次编号,编号为

i

的点的权值为

W_{i}

，每条边的长度均为

1

。图上两点

(u, v)

的距离定义为

u

点到

v

点的最短距离。对于图

G

上的点对

(u, v)

，若它们的距离为

2

，则它们之间会产生

W_{v} \times W_{u}

的联合权值。请问图

G

上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

输入格式

第一行包含 $1$ 个整数 $n$ 。
接下来 $n - 1$ 行,每行包含 $2$ 个用空格隔开的正整数 $u, v$ ，表示编号为 $u$ 和编号为 $v$ 的点之间有边相连。
最后 $1$ 行,包含 $n$ 个正整数，每两个正整数之间用一个空格隔开，其中第 $i$ 个整数表示图 $G$ 上编号为 $i$ 的点的权值为 $W_{i}$ 。

输出格式

输出共 $1$ 行,包含 $2$ 个整数，之间用一个空格隔开,依次为图 $G$ 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对 $10007$ 取余。

样例一

input

output

20 74

explanation

距离为 2 的有序点对有 $(1, 3), (2, 4), (3, 1), (3, 5), (4, 2), (5, 3)$ 。其联合权值分别为 $2, 15, 2, 20, 15, 20$ 。其中最大的是 $20$ ，总和为 $74$ 。

限制与约定

对于30%的数据， $1 < n \leq 100$ ；
对于60%的数据， $1 < n \leq 2000$ ；
对于100%的数据， $1 < n \leq 200000, 0 < W_{i} \leq 10000$ 。
保证一定存在可产生联合权值的有序点对。
时间限制： $1 s$
内存限制： $128 MB$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod = 10007;
int first[233333], next[500000], tot = 0, num[233333], sum[233333], maxx = -1;
struct qer
{
	int from, to;
}q[500000];
struct maxmin
{
	int mx, mn;
}mm[233333];
void build(int f, int t)
{
	q[++tot] = (qer){f, t};
	next[tot] = first[f];
	first[f] = tot;
}
int main()
{
	memset(first, -1, sizeof(first));
	int n;
	cin>>n;
	int u, v;
	for(int i = 1;i < n;i ++)
	{
		scanf("%d%d", &u, &v);
		build(u, v);
		build(v, u);
	}
	for(int i = 1;i <= n;i ++)
		scanf("%d", &num[i]);
	for(int i = 1;i <= n;i ++)
	{
		for(int j = first[i];j != -1;j = next[j])
		{
			int u = q[j].to;
			sum[i] += num[u];
			sum[i] %= mod;
			if(num[u] >= mm[i].mx)
			{
				mm[i].mn = mm[i].mx;
				mm[i].mx = num[u];
			}
			else if(num[u] > mm[i].mn)
				mm[i].mn = num[u];
		}
	}
	long long ans = 0, lsans;
	for(int i = 1;i <= n;i ++)
	{
		for(int j = first[i];j != -1;j = next[j])
		{
			int v = q[j].to;
			lsans = (sum[i] - num[v])*num[v];
			lsans+=mod*10;
//			cout<<lsans<<" lsans   v   "<<v<<" sum[i] "<<sum[i]<<" num[v] "<<num[v]<<endl;
			ans += lsans;
			ans %= mod;
		}
		maxx = max(maxx, mm[i].mx * mm[i].mn);
	}
	while(ans<0)
		ans+=mod;
	cout<<maxx<<" "<<ans;
	return 0;
}