yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

D - Erase Leaves / トヨタ自動車プログラミングコンテスト2023#8 (AtCoder Beginner Contest 333)

ABC333 AtCoder C++ AtCoder Beginner Contest 400点 グラフ 木構造 DP 再帰 競技プログラミング

問題

n 個の頂点からなる木構造のグラフがあり、 i 番目（ただし、 1 \leq i \leq n -1 ）の辺は頂点 {u}_{i} と頂点 {v}_{i} を結んでいる。

「葉である頂点 v を1つ選び、その頂点と接続されている辺を削除する」という操作を何回でも行えるとき、頂点 1 を削除するのに必要な操作回数の最小値を求めよ。

ただし、「葉」とは接続されている辺の本数が高々1本である頂点のことを指す。

入力

最初の1行に、整数 n が与えられる。

次の n - 1 行の i 行目には、整数 {u}_{i}, {v}_{i} が与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 2 \leq n \leq 3 \times {10}^{5}
  • 1 \leq {u}_{i} \lt {v}_{i} \leq n
  • 与えられるグラフは木構造である。

出力

答えを1行で出力すること。

解法

与えられるグラフは木構造なので、頂点 1 を根として考えます。 このとき、頂点 1 については以下の図のようになっています。

ここで、頂点 1 を削除するためには、頂点 1 を葉にしなければなりません。 そのためには、頂点 1 に接続されている辺の本数を1本以下にする必要があります。

従って、図の青い部分が k 個あったとすると、 k - 1 個分だけ削除すれば頂点 1 を削除することのできる状態になります。 このとき、削除する頂点数を最小にするには、 k 個の箇所のうち、含まれる頂点数が少ないものから順に k - 1 個取ることにより達成できます。

すなわち、頂点 1 を削除した後には、 k 個の箇所のうち、含まれる頂点数が最大の部分のみが残るということになります。 よって、この部分の頂点数を m とすると、 n - m 個の頂点が削除されたことになります。

以上を求めるために、頂点 1 を根としたときに、 \mathrm{dp}_{u} を「頂点 u 以下に含まれる頂点の個数」と定めて、これを求めていきます。

これは頂点 u の子を頂点 v とすると、 \begin{align} \mathrm{dp}_{u} = \sum_{v} \mathrm{dp}_{v} + 1 \end{align} で求めることができます。 ここで、 1 を足しているのは、個数に頂点 u 自身を含めているためです。

これをすべて求めるには、頂点 1 から再帰的に辿っていくことにより、 O(n) の計算量で求めることができます。

そして、頂点 1 を削除するために必要な操作回数は、頂点 1 の子を v とすると、 \begin{align} n - \max_{v} \mathrm{dp}_{v} \end{align} によって計算することができます。

以上の方法で、この問題を O(n) 程度の計算量で解くことができ、実行時間制限にも十分間に合います。

ソースコード

まず、グラフが与えられている状態で、 \mathrm{dp}_{u} の値を求める dfs() 関数を以下のように実装しました。

int dp[int(3e5 + 5)];
vector<int> graph[int(3e5 + 5)];

int dfs(int now_node, int before_node = -1) {
  // now_node は現在の頂点を、 before_node は前に見ていた頂点を表す

  dp[now_node] = 1; // 頂点数に自身を含める

  // 頂点 now_node に接続されている頂点について for ループを回す
  for (int next_node : graph[now_node]) {
    if (next_node == before_node) { // next と before が一致するとき、next は親に当たるので、無視する
      continue;
    }
    dp[now_node] += dfs(next_node, now_node); // 子となる next の頂点数を再帰的に求め、足していく
  }

  return dp[now_node];
}

この dfs() 関数が実装されている状態で、答えを出力する部分を以下のように main() 関数の中に直接実装しました。

int n, dp[int(3e5 + 5)];
vector<int> graph[int(3e5 + 5)];

int main() {
  // 値の入力
  cin >> n;
  // グラフの作成
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  int m = 0;
  for (int i : graph[1]) {
    // 頂点 1 の子について、dfs を用いて頂点数を求めて m の値を更新する
    m = max(m, dfs(i, 1));
  }

  cout << n - m << endl; // 答えの出力

  return 0;
}

感想

木構造での探索で再帰を使うものに関して、以前は この問題 での visited のような「その頂点を探索したかを表す bool 値」を用意して行っていました。 （この問題は木構造でもなければ有向グラフでもあるので、例として出すのは間違っているかもしれませんが…。）

現在は この問題 のように「前に探索した頂点」を引数に入れることによって、コードを書く量自体は少し減ったのかなと思っています。

正直、どちらの方法でも特に問題は無いと思いますが、現在扱っている方法の場合は「根が決まっている」ことが前提になる部分もあるので、少し実装に気をつけたいですね。