Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MaxN = (int)5e4 + 10;
- const int ROOT = 1;
- int n, en, c[MaxN], ptr;
- long long ans[MaxN], sz[MaxN];
- int in[MaxN], out[MaxN], timer;
- long long fenwp[MaxN], fenwc[MaxN];
- vector < long long > edge[MaxN];
- vector < pair < int, int > > g[MaxN];
- vector < vector < long long > > downSize, upSize;
- vector < pair < long long, int > > vin[MaxN], vout[MaxN];
- vector < pair < pair < int, int >, pair < long long, int > > > queries;
- long long calcBinarySearch(const vector < vector < long long > > &f, long long R, long long sign) {
- if (f.empty()) {
- return 0LL;
- }
- long long res = 0;
- int sz = (int)f.size();
- int l = 0, r = sz - 1, p = -1;
- while (l <= r) {
- int m = (l + r) / 2;
- if ((f[m][0] - R / 2) * sign <= 0) {
- p = m;
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- if (sign == +1) {
- res += 2 * (p >= 0 ? f[p][2] : 0LL) + R * (f[sz - 1][1] - (p >= 0 ? f[p][1] : 0LL)) - f[sz - 1][2];
- } else {
- res += -2 * (p >= 0 ? f[p][2] : 0LL) + R * (p >= 0 ? f[p][1] : 0LL) + f[sz - 1][2];
- }
- return res;
- }
- void dfs(int v, int p) {
- in[v] = ++timer;
- sz[v] = c[v];
- for (auto to : g[v]) {
- if (to.first == p) {
- continue;
- }
- dfs(to.first, v);
- sz[v] += sz[to.first];
- }
- out[v] = timer;
- }
- void dfsSolve(int v, int p, int e = 0) {
- if (p > 0) {
- edge[in[v]] = {sz[v], e};
- } else {
- edge[in[v]] = {0, 0};
- }
- for (int i = 0; i < (int)g[v].size(); ++i) {
- pair < int, int > to = g[v][i];
- if (to.first == p) {
- continue;
- }
- long long L = sz[to.first], R = sz[ROOT] - sz[to.first];
- queries.push_back(make_pair(make_pair(in[to.first], out[to.first]), make_pair(L, ++ptr)));
- if (1 <= in[to.first] - 1) {
- queries.push_back(make_pair(make_pair(1, in[to.first] - 1), make_pair(R, ptr)));
- }
- if (out[to.first] + 1 <= n) {
- queries.push_back(make_pair(make_pair(out[to.first] + 1, n), make_pair(R, ptr)));
- }
- ans[ptr] -= calcBinarySearch(downSize, R, -1);
- ans[ptr] += calcBinarySearch(upSize, R, 1);
- downSize.push_back({sz[to.first], to.second, 1LL * sz[to.first] * to.second});
- if (downSize.size() > 1) {
- downSize[downSize.size() - 1][1] += downSize[downSize.size() - 2][1];
- downSize[downSize.size() - 1][2] += downSize[downSize.size() - 2][2];
- }
- upSize.push_back({sz[ROOT] - sz[to.first], to.second, 1LL * (sz[ROOT] - sz[to.first]) * to.second});
- if (upSize.size() > 1) {
- upSize[upSize.size() - 1][1] += upSize[upSize.size() - 2][1];
- upSize[upSize.size() - 1][2] += upSize[upSize.size() - 2][2];
- }
- dfsSolve(to.first, v, to.second);
- downSize.pop_back();
- upSize.pop_back();
- }
- }
- template < class T >
- void upd(T fenw[], int r, T val) {
- while (r <= n) {
- fenw[r] += val;
- r |= r + 1;
- }
- }
- template < class T >
- T get(T fenw[], int r) {
- T ans = T(0);
- while (r >= 0) {
- ans += fenw[r];
- r &= r + 1, --r;
- }
- return ans;
- }
- int fnd(const vector < long long >& idx, long long x) {
- return upper_bound(idx.begin(), idx.end(), x) - idx.begin() - 1;
- }
- void Process(const vector < pair < pair < int, int >, pair < long long, int > > >& queries) {
- vector < long long > toCompress;
- for (int i = 1; i <= n; ++i) {
- toCompress.push_back(edge[i][0]);
- }
- sort(toCompress.begin(), toCompress.end());
- toCompress.resize(unique(toCompress.begin(), toCompress.end()) - toCompress.begin());
- for (auto it : queries) {
- int l = it.first.first, r = it.first.second, where = it.second.second;
- long long k = it.second.first;
- vin[l].push_back(make_pair(k, where));
- vout[r].push_back(make_pair(k, where));
- }
- long long b01 = 0, b1 = 0;
- for (int i = 1; i <= n; ++i) {
- for (auto it : vin[i]) {
- long long k = it.first;
- int where = it.second, p = fnd(toCompress, k / 2);
- ans[where] -= 2 * get(fenwp, p) + k * (b1 - get(fenwc, p)) - b01;
- }
- b01 += edge[i][0] * edge[i][1];
- b1 += edge[i][1];
- upd(fenwp, fnd(toCompress, edge[i][0]), edge[i][0] * edge[i][1]);
- upd(fenwc, fnd(toCompress, edge[i][0]), edge[i][1]);
- for (auto it : vout[i]) {
- long long k = it.first;
- int where = it.second, p = fnd(toCompress, k / 2);
- ans[where] += 2 * get(fenwp, p) + k * (b1 - get(fenwc, p)) - b01;
- }
- }
- for (int i = 0; i <= n; ++i) {
- vin[i].clear();
- vout[i].clear();
- fenwp[i] = fenwc[i] = 0;
- }
- }
- void solve() {
- scanf("%d", &n);
- en += n;
- assert (2 <= n && n <= 50000 && en <= 250000);
- for (int i = 1; i <= n; ++i) {
- scanf("%d", &c[i]);
- assert (1 <= c[i] && c[i] <= 50000);
- }
- for (int i = 0; i < n - 1; ++i) {
- int x, y, w;
- scanf("%d%d%d", &x, &y, &w);
- assert (x != y);
- assert (1 <= x && x <= n);
- assert (1 <= y && y <= n);
- assert (1 <= w && w <= 50000);
- g[x].push_back(make_pair(y, w));
- g[y].push_back(make_pair(x, w));
- }
- dfs(ROOT, 0);
- dfsSolve(ROOT, 0);
- Process(queries);
- long long answer = (1ULL << 63) - 1;
- assert (ptr == n - 1);
- assert (timer == n);
- for (int i = 1; i < n; ++i) {
- answer = min(answer, ans[i]);
- }
- printf("%lld\n", answer);
- for (int i = 1; i <= n; ++i) {
- g[i].clear();
- edge[i].clear();
- ans[i] = 0;
- }
- queries.clear();
- timer = ptr = 0;
- }
- int main() {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- int t;
- scanf("%d", &t);
- assert (1 <= t && t <= 250000);
- while (t --> 0) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement