DuongNhi99

DISTRIBUTE

Nov 27th, 2020 (edited)
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1000000007;
  5. const int N = 1e4 + 5;
  6.  
  7. int n, m;
  8. int pa[N], f[N] = {1}, p[N];
  9. vector<int> cnt;
  10. vector<int> edge[N];
  11.  
  12. void DFS(int u, int pa) {
  13.     f[u] = 1;
  14.  
  15.     for (int v : edge[u]) {
  16.         if (v == pa) continue;
  17.         DFS(v, u);
  18.         f[u] += f[v];
  19.         cnt.push_back(f[v] * (n - f[v]));
  20.     }
  21. }
  22.  
  23. int main() {
  24.     ios_base::sync_with_stdio(false);
  25.     cin.tie(NULL); cout.tie(NULL);
  26.  
  27.     cin >> n;
  28.     for (int i = 1; i <= n - 1; ++i) {
  29.         int u, v; cin >> u >> v;
  30.         edge[u].push_back(v);
  31.         edge[v].push_back(u);
  32.     }
  33.  
  34.     DFS(1, 1);
  35.     cin >> m;
  36.     for (int i = 1; i <= m; ++i) cin >> p[i];
  37.     sort(p + 1, p + 1 + n, greater<int>());
  38.     sort(cnt.begin(), cnt.end(), greater<int>());
  39.  
  40.     int pos = 0;
  41.     while (m - pos < n - 1) {
  42.         p[++m] = 1;
  43.     }
  44.     while (m - pos > n - 1) {
  45.         p[pos + 1] += p[pos];
  46.         ++pos;
  47.     }
  48.  
  49.     int ans = 0;
  50.     for (int i = pos; i <= m; ++i) {
  51.         ans += (p[i] * cnt[i - pos - 1]) % MOD;
  52.     }
  53.  
  54.     cout << ans % MOD;
  55.     return 0;
  56. }
Add Comment
Please, Sign In to add comment