問題を言い換えるのが少し難しい
問題概要
頂点数 の木が与えられる(頂点番号 )。
この木に対して「葉を 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; }