C. Link Cut Centroids ～木の重心～

• 問題説明

重心が1つのみの木を作りたい。辺を1つ削除し、辺を1つ追加して新たな木としてよい時、それは可能。その操作（辺の追加・削除）を構築せよ

• Quiz
  • https://codeforces.com/contest/1406/problem/C
• AC
  • https://codeforces.com/contest/1406/submission/95506541
• 解説
  • centroid 1つならOK
  • centroid 2つならそれぞれの部分木のサイズがN/2なので、片方からleafを奪い、もう片方に付ける

• その他
  • 木の重心を求める関数を使いました記念
  • 下記のコドフォURL内の関数を微修正したのみ。centroidを求めるコードの理解はしていない

// 木の重心（最大2つ）
// https://codeforces.com/blog/entry/57593
VI Centroid(const VV &g) {
  int n = g.size();
  VI centroid;
  VI sz(n);
  function<void (int, int)> dfs = [&](int u, int prev) {
    sz[u] = 1;
    bool is_centroid = true;
    for (auto v : g[u]) if (v != prev) {
      dfs(v, u);
      sz[u] += sz[v];
      if (sz[v] > n / 2) is_centroid = false;
    }
    if (n - sz[u] > n / 2) is_centroid = false;
    if (is_centroid) centroid.push_back(u);
  };
  dfs(0, -1);
  return centroid;
}

蟻本

• 蟻本v2 p320に「木の重心分解」について書いてある