Problem D

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
vector<bool> used;
vector<vi> T;
map<pii, ll> w;
const ll MOD = 1'000'000'007;
void dfs(int u) {
    int par = -1;
    ll weight = 0;
    for (int v : T[u]) {
        if (!used[v]) {
            used[v] = true;
            dfs(v);
            weight += w[{u, v}];
        } else { par = v; }
    }
    if (par != -1) {
        w[{par, u}] = weight + 1;
        w[{u, par}] = T.size() - weight - 1;
    }
}
vector<ll> get_weights() {
    vector<ll> weights;
    for (int u = 0; u < T.size(); ++u) {
        for (int v : T[u]) {
            if (u < v) weights.push_back(w[{u, v}] * w[{v, u}]);
        }
    }
    sort(weights.rbegin(), weights.rend());
    return weights;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        T = vector<vi>(n);
        used = vector<bool> (n, false);
        w = map<pii, ll>();
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            T[u-1].push_back(v-1);
            T[v-1].push_back(u-1);
        }
        int m;
        cin >> m;
        vi factors(m);
        for (int& k : factors) cin >> k;
        sort(factors.rbegin(), factors.rend());
        dfs(0);
        vector<ll> W = get_weights();
        vector<ll> lab(W.size(), 1);
        int f = max(0, (int) factors.size() - (int) W.size());
        for (int i = 0; i < f; ++i) {
            lab[0] = (lab[0] * factors[i]) % MOD;
        }
        for (int i = f; i < factors.size(); ++i) {
            lab[i - f] = (lab[i - f] * factors[i]) % MOD;
        }
        ll total = 0;
        for (int i = 0; i < W.size(); ++i)
            total = (total + lab[i] * W[i]) % MOD;
        cout << total << endl;
    }
    return 0;
}