Advertisement
tumaryui

Untitled

Aug 21st, 2020
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. const int mod = 1e9 + 7;
  7. const double pi = acos(-1);
  8.  
  9. vector<vector<int>> gr;
  10. vector<int> sz, muls, primes;
  11. int n, m;
  12. long long mul(long long a,long long n)
  13. {
  14. long long ret;
  15. if(n==0)
  16. return 0;
  17. ret=mul(a,n/2);
  18. ret=(ret+ret)%mod;
  19. if(n%2)
  20. ret=(ret+a)%mod;
  21. return ret;
  22. }
  23.  
  24. void dfs1(int v, int pr = -1) {
  25. sz[v] = 1;
  26. for(auto it: gr[v]) {
  27. if(it != pr) {
  28. dfs1(it, v);
  29. sz[v] += sz[it];
  30. }
  31. }
  32. }
  33.  
  34. void dfs2(int v, int pr = -1) {
  35. for(auto it: gr[v]) {
  36. if(it != pr) {
  37. muls.push_back(sz[it] * (n - sz[it]));
  38. dfs2(it, v);
  39. }
  40. }
  41. }
  42.  
  43. void sol() {
  44. //sol
  45. cin >> n;
  46. gr = vector<vector<int>> (n + 1, vector<int> ());
  47. sz = vector<int> (n + 1, 0);
  48. muls = vector<int> ();
  49. for(int i = 1; i < n; i++) {
  50. int l, r;
  51. cin >> l >> r;
  52. gr[l].push_back(r);
  53. gr[r].push_back(l);
  54. }
  55. dfs1(1);
  56. dfs2(1);
  57. cin >> m;
  58. primes = vector<int> (m);
  59. for(int i = 0; i < m; i++) {
  60. cin >> primes[i];
  61. }
  62. sort(primes.begin(), primes.end());
  63. sort(muls.begin(), muls.end());
  64. int ans = 0;
  65. while(primes.size() > muls.size()) {
  66. int last = primes.back();
  67. primes.pop_back();
  68. primes.back() = mul(primes.back(), last);
  69. }
  70. while(primes.size() > 0) {
  71. ans = (ans + mul(primes.back(), muls.back())) % mod;
  72. muls.pop_back();
  73. primes.pop_back();
  74. }
  75. while(!muls.empty()) {
  76. ans = (ans + muls.back()) % mod;
  77. muls.pop_back();
  78. }
  79. cout << ans << endl;
  80. }
  81.  
  82. signed main() {
  83. ios_base::sync_with_stdio(0);
  84. cin.tie(0);
  85. cout.tie(0);
  86. int t;
  87. cin >> t;
  88. while(t--) {
  89. sol();
  90. }
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement