分析

每条边的边权为 ，由于输入的图是一颗树，那么 之间有且仅有一条简单路径，所以合法的点对 中间只会有一个点。所以考虑枚举中间的节点。令 表示节点 为中间节点的权值之和，那么 。因为 ，所以可以先考虑有序点对的值最后再 就好了。所以 ， 表示在 为中间点， 为当前考虑点，已经计算过的权值之和。由于总的枚举数等于度数 ，所以时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 200010,p = 10007;
LL read() {LL x;scanf("%lld",&x);return x;}
LL w[N],Max = 0,Sum = 0;
vector<int> G[N];
int main() {
    LL n = read();
    for(int i = 1;i < n;i++) {
        LL a = read(),b = read();
        G[a].push_back(b);G[b].push_back(a);
    }
    for(int i = 1;i <= n;i++) w[i] = read();
    for(int i = 1;i <= n;i++) {
        LL Mx = 0,sum = 0;
        for(auto y:G[i]) {
            Max = max(Max,Mx * w[y]);(Sum += sum * w[y]) %= p;
            sum += w[y];Mx = max(Mx,w[y]);
        } 
    }
    printf("%lld %lld\n",Max,(Sum * 2) % p);
    return 0;
}