无向连通图 (G) 有 (n) 个点，(n−1) 条边。点从 (1) 到 (n) 依次编号,编号为 (i) 的点的权值为 (W_i)，每条边的长度均为 (1)。图上两点 ((u, v)) 的距离定义为 (u) 点到 (v) 点的最短距离。对于图 (G) 上的点对 ((u, v))，若它们的距离为 (2)，则它们之间会产生(W_v imes W_u) 的联合权值。
请问图 (G) 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
首先我们注意第一句话，说的那么复杂，其实就告诉我们，这是一棵无根树，再看问题，统计所有距离为2的点对的权值乘积之和及最大值，要就是一张图只能爆搜，但是树，我们可以直接枚举点，显然距离为２的点对之间有且只有一个节点，不存在两个点之间有多条路径，这是树的性质决定的，也就是说显然不会出现重复统计。因此我们只需要枚举每个点，从这个点出发到达的所有点两两之间都可以组成答案。
直接暴力枚举显然不行，(n^2)复杂度显然过不去，但是我们可以采用一些优化，是一种类似于前缀和的思想。
假设现在我们枚举点u，而点u有若干个儿子，我们用邻接表存图可以得到一个儿子的序列，假设我们现在访问到儿子v，那么儿子v对答案的贡献就是前面访问的所有儿子的权值与当前点v权值乘积之和，前面所有儿子的权值之和显然可以前缀和优化一下，这样无序点对的所有答案就可以求出来了，而题中要求出有序的，因此答案*2即可。
再考虑最大值，这里需要一些贪心的思路，我们统计时维护前缀最大值，这个最大值和当前枚举的儿子v之间就有可能产生最大值，然后更新前缀最大值和答案就行了。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<set>
#include<queue>
#include<vector>
#include<string>
#pragma GCC optimaze(2)
#pragma GCC optimaze(3)
using namespace std;
#define P system("pause");
#define B printf("Break
");
#define A(x) cout << #x << " " << (x) << endl;
#define AA(x,y) cout << #x << " " << (x) << " " << #y << " " << (y) << endl;
#define ll long long
#define inf 1000000000
#define linf 10000000000000000
int read()
{
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return f * x;
}
#define N 200010
#define mod 10007
ll val[N],n;
vector<int>g[N];
int main()
{
n = read();
for(int i = 1;i < n;i++)
{
int u = read(),v = read();
g[u].push_back(v);
g[v].push_back(u);
}
ll Max = 0,ans = 0;
for(int i = 1;i <= n;i++) val[i] = read();
for(int u = 1;u <= n;u++)
{
ll sum = 0,tp = 0;
for(int j = 0;j < g[u].size();j++)
{
int v = g[u][j];
Max = max(Max,tp * val[v]);
tp = max(tp,val[v]);
ans += val[v] * sum % mod;
sum += val[v];
}
}
cout << Max << " " << ans * 2 % mod << endl;
}