Advertisement
Guest User

Untitled

a guest
Feb 19th, 2018
257
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.30 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MaxN = (int)5e4 + 10;
  6. const int ROOT = 1;
  7.  
  8. int n, en, c[MaxN], ptr;
  9. long long ans[MaxN], sz[MaxN];
  10. int in[MaxN], out[MaxN], timer;
  11. long long fenwp[MaxN], fenwc[MaxN];
  12. vector < long long > edge[MaxN];
  13. vector < pair < int, int > > g[MaxN];
  14. vector < vector < long long > > downSize, upSize;
  15. vector < pair < long long, int > > vin[MaxN], vout[MaxN];
  16. vector < pair < pair < int, int >, pair < long long, int > > > queries;
  17.  
  18. long long calcBinarySearch(const vector < vector < long long > > &f, long long R, long long sign) {
  19. if (f.empty()) {
  20. return 0LL;
  21. }
  22. long long res = 0;
  23. int sz = (int)f.size();
  24. int l = 0, r = sz - 1, p = -1;
  25. while (l <= r) {
  26. int m = (l + r) / 2;
  27. if ((f[m][0] - R / 2) * sign <= 0) {
  28. p = m;
  29. l = m + 1;
  30. } else {
  31. r = m - 1;
  32. }
  33. }
  34. if (sign == +1) {
  35. res += 2 * (p >= 0 ? f[p][2] : 0LL) + R * (f[sz - 1][1] - (p >= 0 ? f[p][1] : 0LL)) - f[sz - 1][2];
  36. } else {
  37. res += -2 * (p >= 0 ? f[p][2] : 0LL) + R * (p >= 0 ? f[p][1] : 0LL) + f[sz - 1][2];
  38. }
  39. return res;
  40. }
  41.  
  42. void dfs(int v, int p) {
  43. in[v] = ++timer;
  44. sz[v] = c[v];
  45. for (auto to : g[v]) {
  46. if (to.first == p) {
  47. continue;
  48. }
  49. dfs(to.first, v);
  50. sz[v] += sz[to.first];
  51. }
  52. out[v] = timer;
  53. }
  54.  
  55. void dfsSolve(int v, int p, int e = 0) {
  56. if (p > 0) {
  57. edge[in[v]] = {sz[v], e};
  58. } else {
  59. edge[in[v]] = {0, 0};
  60. }
  61. for (int i = 0; i < (int)g[v].size(); ++i) {
  62. pair < int, int > to = g[v][i];
  63. if (to.first == p) {
  64. continue;
  65. }
  66. long long L = sz[to.first], R = sz[ROOT] - sz[to.first];
  67. queries.push_back(make_pair(make_pair(in[to.first], out[to.first]), make_pair(L, ++ptr)));
  68. if (1 <= in[to.first] - 1) {
  69. queries.push_back(make_pair(make_pair(1, in[to.first] - 1), make_pair(R, ptr)));
  70. }
  71. if (out[to.first] + 1 <= n) {
  72. queries.push_back(make_pair(make_pair(out[to.first] + 1, n), make_pair(R, ptr)));
  73. }
  74. ans[ptr] -= calcBinarySearch(downSize, R, -1);
  75. ans[ptr] += calcBinarySearch(upSize, R, 1);
  76. downSize.push_back({sz[to.first], to.second, 1LL * sz[to.first] * to.second});
  77. if (downSize.size() > 1) {
  78. downSize[downSize.size() - 1][1] += downSize[downSize.size() - 2][1];
  79. downSize[downSize.size() - 1][2] += downSize[downSize.size() - 2][2];
  80. }
  81. upSize.push_back({sz[ROOT] - sz[to.first], to.second, 1LL * (sz[ROOT] - sz[to.first]) * to.second});
  82. if (upSize.size() > 1) {
  83. upSize[upSize.size() - 1][1] += upSize[upSize.size() - 2][1];
  84. upSize[upSize.size() - 1][2] += upSize[upSize.size() - 2][2];
  85. }
  86. dfsSolve(to.first, v, to.second);
  87. downSize.pop_back();
  88. upSize.pop_back();
  89. }
  90. }
  91.  
  92. template < class T >
  93. void upd(T fenw[], int r, T val) {
  94. while (r <= n) {
  95. fenw[r] += val;
  96. r |= r + 1;
  97. }
  98. }
  99.  
  100. template < class T >
  101. T get(T fenw[], int r) {
  102. T ans = T(0);
  103. while (r >= 0) {
  104. ans += fenw[r];
  105. r &= r + 1, --r;
  106. }
  107. return ans;
  108. }
  109.  
  110. int fnd(const vector < long long >& idx, long long x) {
  111. return upper_bound(idx.begin(), idx.end(), x) - idx.begin() - 1;
  112. }
  113.  
  114. void Process(const vector < pair < pair < int, int >, pair < long long, int > > >& queries) {
  115. vector < long long > toCompress;
  116. for (int i = 1; i <= n; ++i) {
  117. toCompress.push_back(edge[i][0]);
  118. }
  119. sort(toCompress.begin(), toCompress.end());
  120. toCompress.resize(unique(toCompress.begin(), toCompress.end()) - toCompress.begin());
  121. for (auto it : queries) {
  122. int l = it.first.first, r = it.first.second, where = it.second.second;
  123. long long k = it.second.first;
  124. vin[l].push_back(make_pair(k, where));
  125. vout[r].push_back(make_pair(k, where));
  126. }
  127. long long b01 = 0, b1 = 0;
  128. for (int i = 1; i <= n; ++i) {
  129. for (auto it : vin[i]) {
  130. long long k = it.first;
  131. int where = it.second, p = fnd(toCompress, k / 2);
  132. ans[where] -= 2 * get(fenwp, p) + k * (b1 - get(fenwc, p)) - b01;
  133. }
  134. b01 += edge[i][0] * edge[i][1];
  135. b1 += edge[i][1];
  136. upd(fenwp, fnd(toCompress, edge[i][0]), edge[i][0] * edge[i][1]);
  137. upd(fenwc, fnd(toCompress, edge[i][0]), edge[i][1]);
  138. for (auto it : vout[i]) {
  139. long long k = it.first;
  140. int where = it.second, p = fnd(toCompress, k / 2);
  141. ans[where] += 2 * get(fenwp, p) + k * (b1 - get(fenwc, p)) - b01;
  142. }
  143. }
  144. for (int i = 0; i <= n; ++i) {
  145. vin[i].clear();
  146. vout[i].clear();
  147. fenwp[i] = fenwc[i] = 0;
  148. }
  149. }
  150.  
  151. void solve() {
  152. scanf("%d", &n);
  153. en += n;
  154. assert (2 <= n && n <= 50000 && en <= 250000);
  155. for (int i = 1; i <= n; ++i) {
  156. scanf("%d", &c[i]);
  157. assert (1 <= c[i] && c[i] <= 50000);
  158. }
  159. for (int i = 0; i < n - 1; ++i) {
  160. int x, y, w;
  161. scanf("%d%d%d", &x, &y, &w);
  162. assert (x != y);
  163. assert (1 <= x && x <= n);
  164. assert (1 <= y && y <= n);
  165. assert (1 <= w && w <= 50000);
  166. g[x].push_back(make_pair(y, w));
  167. g[y].push_back(make_pair(x, w));
  168. }
  169. dfs(ROOT, 0);
  170. dfsSolve(ROOT, 0);
  171. Process(queries);
  172. long long answer = (1ULL << 63) - 1;
  173. assert (ptr == n - 1);
  174. assert (timer == n);
  175. for (int i = 1; i < n; ++i) {
  176. answer = min(answer, ans[i]);
  177. }
  178. printf("%lld\n", answer);
  179. for (int i = 1; i <= n; ++i) {
  180. g[i].clear();
  181. edge[i].clear();
  182. ans[i] = 0;
  183. }
  184. queries.clear();
  185. timer = ptr = 0;
  186. }
  187.  
  188. int main() {
  189. // freopen("input.txt", "r", stdin);
  190. // freopen("output.txt", "w", stdout);
  191. int t;
  192. scanf("%d", &t);
  193. assert (1 <= t && t <= 250000);
  194. while (t --> 0) {
  195. solve();
  196. }
  197. return 0;
  198. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement