AIで解説 AtCoder攻略　木DP・LCA

木DP・LCAページの位置づけ

項目	内容
必修度	重要
学習目安	標準〜発展
前提	DFS・再帰・累積値
対象問題	57問（推定値あり57問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	1
標準	0〜799	8
標準〜発展	800〜1199	10
発展	1200以上	38
未算出	—	0

木には閉路がないため、根からのDFS、部分木DP、LCA、直径、全方位DPを同じ隣接リストから組み立てられます。木専用の「親へ戻らない」実装を身につけます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

木DP・LCAの見分け方

頂点数が辺数+1の木である
根から子へ情報を渡し、帰りがけに集約できる
全頂点を始点にした答えを再計算せず求めたい

木DP・LCAの実装前チェック

親頂点を引数にして逆向きの辺をたどらない
部分木の値を返すタイミングを決める
根を変えたときに再利用できる値を分ける

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC263 B Ancestor（公式解説）を解きます。各頂点の親をたどり、頂点Nから根1まで何回移動するかを数えます。木全体を探索する必要はありません。

N = int(input())
parent = [0] + [value - 1 for value in map(int, input().split())]
current = N - 1
answer = 0
while current != 0:
    current = parent[current]
    answer += 1
print(answer)

親をたどる回数をDとするとO(D)時間・O(N)メモリです。

木DP・LCAの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC263 B Ancestor	公式解説	親ポインタを根までたどり、祖先の段数を数える。	-32
ABC451 C Understory	公式解説	Peel leaves from the tree until the understory condition is satisfied.	250
ABC274 C Ameba	公式解説	Build the parent tree from each ameba’s children and compute each ameba’s generation depth.	304
ABC423 C Lock All Doors	公式解説	公式Editorialの方針を lock all doors tree dp として整理する。	376
ABC270 C Simple path	公式解説	木を探索して親を記録し、始点から終点までの経路を復元する。	625

次に解く

問題	公式解説	出題意図	difficulty
ABC209 D Collision	公式解説	Color the tree by depth parity; two vertices are odd-distance apart exactly when their colors differ.	686
ABC333 D G. Erase Leaves	公式解説	Remove leaves repeatedly; the remaining structure determines the deleted labels.	704
ABC213 D G. Takahashi Tour	公式解説	隣接頂点を番号順に訪れるDFSで、頂点へ到着するたびに記録するオイラーツアーを作る。	710
ABC243 D G. Moves on Binary Tree	公式解説	Uと直前のL/Rを相殺するスタックで操作列を短縮し、残った移動をXへ適用する。	758
ABC368 D G. Minimum Steiner Tree	公式解説	Official editorial intent is classified as steiner tree pruning.	816

挑戦問題

問題	公式解説	出題意図	difficulty
ABC138 D Ki	公式解説	各頂点への加算を一度ため、根から子へ親の累積値を伝播して全頂点の最終値を求める。	920
ABC309 E H. Family and Insurance	公式解説	Propagate the maximum active insurance depth from each parent to descendants.	957
ABC240 E H. Ranges on Tree	公式解説	DFSの訪問順で各部分木の最小・最大番号を記録し、部分木を区間として表す。	1068
ABC239 E H. Subtree K-th Max	公式解説	部分木ごとの値をDFS帰りがけにマージし、上位20個だけ保持してK番目最大を答える。	1084
ABC303 E H. A Gift From the Stars	公式解説	Use the forced degree pattern of a subdivided star to recover branch lengths.	1113