题解 | #[NOIP2014]联合权值#

本题不能使用常规做法树形dp，因为相互之间没有联系，无法找到动态转换方程。
所以我们换个思路，我们尝试遍历每个节点作为中转点，也可以称为根，那么它的两边的节点两两配对就可以符合题目的要求。
我们将两边的节点的权值存入一个数组中，先排序，将数组的最后两个节点相乘就是本次最大的答案，不断更新就行。而且，我们在存入的过程中还要维护一个前缀和，这样我们可以求出和的答案，即$:ans[j]\ast (sum[idx-1]-ans[j]):ans[j]\; *\; (sum[idx\; -\; 1]\; -\; ans[j])$
AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
const long long mod = 10007;
struct node
{
	int to, ne;
} e[3 * N];
int h[N], idx;
void add(int a, int b)
{
	e[++idx].to = b;
	e[idx].ne = h[a];
	h[a] = idx;
}
long long ans[N], sum[N];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	vector<long long> a(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	long long _sum = 0, maxx = 0;
	for (int i = 1; i <= n; i++)
	{
		idx = 0;
		sum[idx++] = 0;
		for (int j = h[i]; j; j = e[j].ne)
		{
			int k = e[j].to;
			ans[idx] = a[k];
			sum[idx] = sum[idx - 1] + ans[idx];
			idx++;
		}
		sort(ans + 1, ans + idx);
		maxx = max(maxx, ans[idx - 1] * ans[idx - 2] % mod);
		for (int j = 1; j < idx; j++)
			_sum = (_sum % mod + ans[j] * (sum[idx - 1] - ans[j]) % mod + mod) % mod;
	}
	cout << maxx << ' ' << _sum % mod << endl;
}