Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int mod = 1e9 + 7;
- const double pi = acos(-1);
- vector<vector<int>> gr;
- vector<int> sz, muls, primes;
- int n, m;
- long long mul(long long a,long long n)
- {
- long long ret;
- if(n==0)
- return 0;
- ret=mul(a,n/2);
- ret=(ret+ret)%mod;
- if(n%2)
- ret=(ret+a)%mod;
- return ret;
- }
- void dfs1(int v, int pr = -1) {
- sz[v] = 1;
- for(auto it: gr[v]) {
- if(it != pr) {
- dfs1(it, v);
- sz[v] += sz[it];
- }
- }
- }
- void dfs2(int v, int pr = -1) {
- for(auto it: gr[v]) {
- if(it != pr) {
- muls.push_back(sz[it] * (n - sz[it]));
- dfs2(it, v);
- }
- }
- }
- void sol() {
- //sol
- cin >> n;
- gr = vector<vector<int>> (n + 1, vector<int> ());
- sz = vector<int> (n + 1, 0);
- muls = vector<int> ();
- for(int i = 1; i < n; i++) {
- int l, r;
- cin >> l >> r;
- gr[l].push_back(r);
- gr[r].push_back(l);
- }
- dfs1(1);
- dfs2(1);
- cin >> m;
- primes = vector<int> (m);
- for(int i = 0; i < m; i++) {
- cin >> primes[i];
- }
- sort(primes.begin(), primes.end());
- sort(muls.begin(), muls.end());
- int ans = 0;
- while(primes.size() > muls.size()) {
- int last = primes.back();
- primes.pop_back();
- primes.back() = mul(primes.back(), last);
- }
- while(primes.size() > 0) {
- ans = (ans + mul(primes.back(), muls.back())) % mod;
- muls.pop_back();
- primes.pop_back();
- }
- while(!muls.empty()) {
- ans = (ans + muls.back()) % mod;
- muls.pop_back();
- }
- cout << ans << endl;
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t;
- cin >> t;
- while(t--) {
- sol();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement