実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 704

問題概要

$N$ 個の頂点からなる木が与えられ、 $i$ 番目の辺は頂点 $u_i$ と $v_i$ を結んでいる。「葉である頂点 $v$ を一つ選び、 $v$ 及びそれに接続する辺を全て削除する」という操作を繰り返すとき、頂点 $1$ を削除するまでに最小で操作を何回行うことになるかを求めよ。

制約

入力はすべて整数。
$2 \leq N \leq 3 \times 10^5$
$1 \leq u_i \lt v_i \leq N$

考察

とりあえず頂点 $1$ を根とする適当な木の図を描いてみよう。

ここで、頂点 $1$ を根とする部分木を考える。

上図では赤、緑、青の3つの部分木ができた。この中から1つを残して、他の部分木の深さが深い頂点から順に削除していく。すると、頂点 $1$ の次数は $1$ (すなわち葉) となるため、これも削除が可能となる。本問は、この段階までに削除する頂点数を最小化するというものだ。

したがって、残す部分木は頂点数が最大のものを選択することになり、答えとしては $N - (残す部分木の頂点数)$ となる。

各部分木の頂点数を求める方法についてだが、これは Union Find という、グループ分けを効率的に管理できるデータ構造を使うと便利である。 AtCoder Library にもdsuという構造体名で実装されている。

頂点 $1$ を除いて辺をmergeすることで部分木を作り、groups()で連結成分 (部分木) を列挙し、size()で連結成分の頂点数を取得できる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    dsu d(N);
    rep(i, 0, N - 1)
    {
        int u, v;
        cin >> u >> v;

        if (u != 1)
            d.merge(u - 1, v - 1);
    }

    int max_group_size = 0;
    for (auto &&g : d.groups())
        chmax(max_group_size, (int)g.size());

    cout << N - max_group_size << endl;
}