fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long 
  4. #define ll long long
  5. const ll M = 1000000007;
  6. #define pb push_back
  7. #define forn(i,k,n) for(int i = k; i < n; ++i)
  8. #define nfor(i,n,k) for(int i = n; i >= k; --i)
  9. #define all(arr) arr.begin(), arr.end()
  10. #define endl '\n'
  11. #define N 100015
  12. ll n;
  13. vector<ll> G[N];
  14. multiset<ll,greater<ll>> s;
  15. vector<ll> C(N);
  16. // dfs function to calculate no of nodes in subtree of u..
  17. // and then inserting the contribution of each edge in the set s
  18. ll dfs(ll u, ll p){
  19. 	C[u] = 0;
  20. 	ll tmp = 0;
  21. 	for(auto x: G[u]){
  22. 		if(x == p) continue;
  23. 		C[x] += dfs(x,u) + 1;
  24. 		C[x] %= M;
  25. 		tmp += C[x];
  26. 		tmp %= M;
  27. 		s.insert(((C[x] % M) * (n - C[x]) % M) % M); // contribution is (subtree nodes * (total nodes - subtree nodes))...
  28. 	}
  29. 	return tmp % M;
  30. }
  31. void solve(){
  32. 	// input and clearing of Data structures
  33. 	s.clear();
  34. 	cin >> n;
  35. 	forn(i,1,n + 1) G[i].clear();
  36. 	C.clear();
  37. 	forn(i,1,n){
  38. 		ll u, v; cin >> u >> v;
  39. 		G[u].pb(v);
  40. 		G[v].pb(u);
  41. 	}
  42. 	dfs(1,0); // dfs to calculate contribution
  43. 	ll m; cin >> m;
  44. 	multiset<ll,greater<ll>> fac; // multiset for factors of k
  45. 	forn(i,0,m){
  46. 		ll xx; cin >> xx;
  47. 		fac.insert(xx);
  48. 	}
  49. 	while(fac.size() < n - 1) fac.insert(1); // inserting 1 for each left nodes if (m < n - 1)
  50. 	ll ans = 0;
  51. 	while(fac.size() > n - 1){     // multiplying greatest factors of k till the size of m is n - 1; if(m > n - 1)
  52. 		ll tmp = *fac.begin();
  53. 		fac.erase(fac.begin());
  54. 		ll tmp2 = *fac.begin();
  55. 		fac.erase(fac.begin());
  56. 		fac.insert(((tmp % M) * (tmp2 % M)) % M);
  57. 	}
  58. 	auto it = fac.begin();
  59. 	// calculating total answer by multiplying contribution of each edge by factors of k (we multiply highest contribution by highest factor))...
  60. 	for(auto x : s){
  61. 		ans += ((x % M) * ((*it) % M)) % M;
  62. 		ans %= M;
  63. 		it++;
  64. 	}
  65. 	cout << ans % M << endl;
  66. }
  67. signed main(){
  68.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  69. 	int t; cin >> t;
  70. 	while(t--) solve();
  71.     return 0;
  72. }
Success #stdin #stdout 0s 6060KB
comments (?)
stdin 
3
4
1 2
2 3
3 4
2
2 2
4
3 4
1 3
3 2
2
3 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3
stdout 
17
18
286
https://ideone.com/2pnA5n
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!