M-SOLUTIONS プロコンオープン D問題：Maximum Sum of Minimum

問題. Maximum Sum of Minimum

頂点からなる木 と，正の整数 が与えられる．全単射 のスコアを各辺 に対して の総和とする．スコアを最大とする全単射を求めよ．

制約： ，　

解法

と仮定する．初めに全単射のスコアの上界が であることを示す．任意の全単射 に対して，各辺の値を降順に並べたものを とする． に対して が誘導する森 を考える．このとき， となる．なぜならば，一般に 頂点， 個の木からなる森の辺数 は となり， のとき，すなわち木のときが辺数を固定したときの頂点数が最も多いので となる．したがって， が成り立つ．

次に，ある全単射でスコアが となるものを構成する．適当な頂点 を根とした根付き木 を考え， とする．次に，下の図のように幅優先探索の訪問順に各頂点に順番に を割り当てる．このとき，任意の頂点 に対して，その親の値は の値よりも大きいので親との間の辺の値は となる．したがって，スコアの上界と一致する全単射を構成することができたので，この全単射が最適解となる．
　　　　　　　

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 0, a, b; i + 1 < n; ++i) {
        cin >> a >> b;
        adj[a - 1].push_back(b - 1);
        adj[b - 1].push_back(a - 1);
    }

    vector<int> c(n);
    for (auto &c_i : c) cin >> c_i;
    sort(c.begin(), c.end(), greater<int>());

    const int root = 0;
    int max_sum = 0, idx = 0;
    vector<int> max_w(n, -1);
    queue<int> que;
    que.push(root);
    max_w[root] = c[idx++];

    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (auto u : adj[cur]) {
            if (max_w[u] != -1) continue;
            max_w[u] = c[idx++];
            max_sum += min(max_w[cur], max_w[u]);
            que.push(u);
        }
    }

    cout << max_sum << endl;
    for (int v = 0; v < n; ++v)
        cout << max_w[v] << " \n"[v == n - 1];

    return 0;
}

上界の証明に時間がかかりすぎていてツラかったので，証明の途中で取り敢えず投げたら AC した（たまたまだったかもしれないので反省）．