Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MOD = 1000000007;
- const int N = 1e4 + 5;
- int n, m;
- int pa[N], f[N] = {1}, p[N];
- vector<int> cnt;
- vector<int> edge[N];
- void DFS(int u, int pa) {
- f[u] = 1;
- for (int v : edge[u]) {
- if (v == pa) continue;
- DFS(v, u);
- f[u] += f[v];
- cnt.push_back(f[v] * (n - f[v]));
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL); cout.tie(NULL);
- cin >> n;
- for (int i = 1; i <= n - 1; ++i) {
- int u, v; cin >> u >> v;
- edge[u].push_back(v);
- edge[v].push_back(u);
- }
- DFS(1, 1);
- cin >> m;
- for (int i = 1; i <= m; ++i) cin >> p[i];
- sort(p + 1, p + 1 + n, greater<int>());
- sort(cnt.begin(), cnt.end(), greater<int>());
- int pos = 0;
- while (m - pos < n - 1) {
- p[++m] = 1;
- }
- while (m - pos > n - 1) {
- p[pos + 1] += p[pos];
- ++pos;
- }
- int ans = 0;
- for (int i = pos; i <= m; ++i) {
- ans += (p[i] * cnt[i - pos - 1]) % MOD;
- }
- cout << ans % MOD;
- return 0;
- }
Add Comment
Please, Sign In to add comment