M-Solutions プロコンオープン D - Maximum Sum of Minimum 解いた感想

問題はこちら。

atcoder.jp

最初、次数の大きい頂点にの大きい値を割り振ればええやろと適当解放を思いつき見事WA。アホ。

解法

結論を言ってしまうと深さ優先探索をして、その順にを大きい値から割り振っていく。

の最大値をとすると、一つの辺にを書き込む事はできない。

次に大きい値をとして、を辺に書き込むことができるかを考えると、の値を持つ頂点との間の辺に書き込むことができる。この作業を続けると、全ての辺に書き込まれた値の合計値はになる。(はの値の合計値）

これが最大値になる理由は自明っぽい。正直いうと説明するのが面倒。詳しく知りたい方は以下のリンクからEditorialを見て。

https://img.atcoder.jp/m-solutions2019/editorial.pdf

最大値を求める計算のところでとんでもなく面倒な計算をしているのは許して。提出したコードは以下。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int id = 0;
vector<int> c;
vector<vector<int>> g;
vector<int> seen;
vector<int> value;
void dfs(int node) {
  if(seen[node]) return;
  seen[node] = 1;
  value[node] = c[id];
  id++;
  for(auto& next : g[node]) {
    if(!seen[next]) dfs(next);
  }
}
int main() {
  int n;
  cin >> n;
  g.resize(n);
  c.resize(n);
  seen.resize(n);
  value.resize(n);
  for(int i=0;i<n-1;i++) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  for(int i=0;i<n;i++) cin >> c[i];
  sort(c.rbegin(), c.rend());
  dfs(0);
  long long m = 0;
  for(int i=0;i<n;i++) {
    for(auto& el : g[i]) {
      m += min(value[i], value[el]);
    }
  }
  cout << m / 2 << endl;
  for(int i=0;i<n;i++) cout << value[i] << endl;
  return 0;
}