AtCoder ABC 333 D - Erase Leaves (2Q, 茶色, 400 点)

問題を言い換えるのが少し難しい

• 問題へのリンク

問題概要

頂点数 の木が与えられる（頂点番号 ）。

この木に対して「葉を 1 つ選んで削除する」という操作を繰り返す。頂点 1 を削除するまでの操作回数の最小値を求めよ。

制約

• 

考えたこと

0-indexed で考える。

下図のように、頂点 0 と繋がっている「固まり」のサイズを考えていこう。

このうちの最大サイズの固まりを除いて、その残りを削除することで、「最小回数の操作で頂点 0 を除去する」ができるようになる。

ここで、頂点 0 を根とした木 DP をして、頂点 0 の子頂点のうち、その頂点を根とした部分木のサイズを求めていき、その最大値を としよう。そうすると が答えとなる。

計算量は である。

コード

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
    int N, u, v;
    cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; i++) {
        cin >> u >> v, u--, v--;
        G[u].push_back(v), G[v].push_back(u);
    }

    // 頂点 0 を根とした木 DP
    vector<int> siz(N, 0);
    auto rec = [&](auto rec, int v, int p) -> int {
        siz[v] = 1;  // 自分自身
        for (auto ch : G[v]) {
            if (ch == p) continue;
            siz[v] += rec(rec, ch, v);
        }
        return siz[v];
    };
    rec(rec, 0, -1);

    // 頂点 0 の子頂点のうち、その子頂点を根とする部分木のサイズが最大のものを残して、他を切り取る
    int max_size = 0;
    for (auto ch : G[0]) max_size = max(max_size, siz[ch]);
    cout << N - max_size << endl;
}