Codeforces 1466D 13th Labour of Heracles

题意

给一棵大小为$n$的树，每个节点有权值$a_i$,对其染色，染色时需保证所有相同颜色的边可以组成一颗树，定义树的权值为其不同颜色的子树上的所有节点的权值和，问染$1$~$n-1$种颜色，每次可以得到最大的树的权值。

分析

每增加一种颜色的时候，因为只有其根节点与其他颜色相邻，所以每次只会增加其根节点的权值，那么每次挑一个拥有最大权值的节点，将其一颗子树染成不同颜色即可，那么最多染其出度减一次（因为只有这么多棵子树），维护一个优先队列和一个出度数组即可。

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int in[maxn], a[maxn];

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    rep(i, 1, n)in[i] = 0, cin >> a[i], sum += a[i];
    priority_queue<pii> q;
    rep(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        ++in[x], ++in[y];
    }
    rep(i, 1, n) {
        if (in[i] >= 2)
            q.push({a[i], i});
    }
    rep(i, 1, n - 1) {
        cout << sum << ' ';
        if (!q.empty()) {
            pii now = q.top();
            q.pop();
            sum += now.first;
            --in[now.second];
            if (in[now.second] > 1)
                q.push({now.first, now.second});
        }
    }
    cout << '\n';
}

signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}