木構造

概要

一意な経路と距離・直径を確認し、根付き木DP・rerootingで部分木と全方位集約を学ぶ。Euler順・LCA・HLD・virtual treeで部分木・祖先・pathを扱う一般的なtoolkitを揃えた後、暗黙の完全二分木を展開せずに数える。続いて包含関係や併合履歴を木にする方法、重心分解、距離からの木の復元、親先行順序の縮約へ進む。後半は多項式木DP、rake・compressによる動的木DP、資源DPを渡すHLRecDPを扱う。多項式木DPでは代数章の畳み込みを先に学ぶ。

木モデルと構造

木固有の根・部分木・path・separator構造へ問題を写し、利用する性質を選ぶ。

考え方

木では任意の二頂点間の単純pathが一つで、辺を切ると二つの独立な側が得られる。この性質を距離、部分木DP、rerooting、path索引、分解のそれぞれで使う。

成立条件と計算量

N頂点の明示木はN−1辺でO(N)走査が基準になる。根の選択は計算用の表現であり、根を変えた答えが必要ならrerootingへ進む。暗黙の巨大木や多項式DPではNだけで費用を決めない。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。探索で得る木の距離・祖先・部分木を、集約と分解の共通の土台にする入口。

対象色の読み方は本書の読み方を参照してください。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-tree

習得する技能

  • 木固有の根・部分木・path・separator構造へ問題を写し、利用する性質を選ぶ。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

一般グラフから独立させ、根・部分木・一意path・separatorという木固有の不変量を体系的に積み上げる。

このUnitでは扱わないもの

  • なし

根拠