👌

【競技プログラミング】AtCoder Beginner Contest 368_D問題(TLE版)

に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc368/tasks/abc368_d

要約

  1. N頂点の木が与えられる。
  2. 頂点には1からNまでの番号がついている。
  3. 辺は頂点AiとBiを結んでいる。
  4. この木から辺と頂点を削除して新しい木を作る。
  5. 新しい木は指定されたK個の頂点（V1, ..., VK）を全て含む必要がある。
    条件を満たす新しい木の中で、頂点数が最小のものを求める。
  • N: 元の木の頂点数
  • Ai, Bi: i番目の辺が結ぶ2つの頂点の番号
  • K: 新しい木に必ず含める必要がある頂点の数
  • V1, ..., VK: 新しい木に必ず含める必要がある頂点の番号

既存投稿一覧ページへのリンク

一覧ページ
AC版(DFS未使用)

アプローチ

深さ優先探索（DFS）を用いて、指定された頂点を全て含む最小の部分木を見つける。
指定された頂点のいずれかを根として、そこから木全体をたどりながら、必要な頂点と経路を特定する。

解法手順

  1. 入力を受け取り、隣接リスト形式でグラフを構築する。

  2. 指定されたK個の頂点を記録するための配列を用意する。

  3. 指定されたK個の頂点のうちの1つ（例えば最初の頂点）を根として選ぶ。

  4. 深さ優先探索（DFS）を実装する：

    • 現在の頂点が指定された頂点の1つであれば、その頂点を含める。
    • 子頂点を再帰的に探索し、指定された頂点につながる経路があれば、その頂点も含める。

  5. DFSの結果を基に、必要な頂点の数（新しい木の頂点数）を数える。

  6. 最小の頂点数を出力する。

ACコード

ac.py
import sys

# 再帰の深さ制限を設定
sys.setrecursionlimit(10**6)

def io_func():
    # 入力を受け取る
    n, k = map(int, input().split())  # nは頂点数、kは指定される頂点の数
    G = [[] for _ in range(n)]  # 隣接リストでグラフを表現
    for _ in range(n-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)  # 0-indexedに調整
        G[b-1].append(a-1)
    V = list(map(int, input().split()))  # 指定されたk個の頂点
    return n, k, G, V

def dfs(v, p, G, selected, ans):
    res = 0
    if selected[v]:
        res = 1  # 現在の頂点が指定された頂点なら含める
    for u in G[v]:
        if u == p:
            continue  # 親頂点はスキップ
        if dfs(u, v, G, selected, ans):
            res = 1  # 子頂点のいずれかが指定された頂点につながっていれば含める
    ans[v] = res  # 結果を記録
    return res

def solve(n, k, G, V):
    selected = [False] * n  # 指定された頂点を記録
    for i in range(k):
        selected[V[i]-1] = True  # 1-indexedから0-indexedに調整

    ans = [-1] * n  # 各頂点が部分木に含まれるかを記録
    dfs(V[0]-1, -1, G, selected, ans)  # 最初の指定頂点を根としてDFS開始

    return sum(ans)  # 部分木に含まれる頂点数を返す

if __name__=="__main__":
    # メイン処理
    n, k, G, V = io_func()  # 入力を受け取る
    result = solve(n, k, G, V)  # 問題を解く
    print(result)  # 結果を出力

###
# n: 頂点の総数
# k: 指定される頂点の数
# G: グラフの隣接リスト表現
# V: 指定されたk個の頂点のリスト
# selected: 各頂点が指定された頂点かどうかを示すブール値のリスト
# ans: 各頂点が最小部分木に含まれるかどうかを示すリスト

# 1. io_func関数: 標準入力から問題のデータを読み取り、必要なデータ構造を構築する。
# 2. dfs関数: 深さ優先探索を行い、指定された頂点を全て含む最小の部分木を見つける。
#    - 現在の頂点が指定された頂点か、または子孫に指定された頂点があれば1を返す。
#    - そうでなければ0を返す。
# 3. solve関数: 問題全体の解決を行う。
#    - 指定された頂点を記録し、DFSを開始する。
#    - DFSの結果から、最小部分木に含まれる頂点数を計算する。
# 4. メイン処理: io_func関数でデータを読み取り、solve関数で問題を解き、結果を出力する。

アルゴリズムトレースメモ

TLEしてしまったので、アプローチ方法は変えるとして、本プログラムのポイント図解





Discussion