木構造
概要
一意な経路と距離・直径を確認し、根付き木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は対象色を目安に後から戻って学べます。
- 基準点からの木距離・剰余類・直径・中心 — 水色
- 木DP・集約・rerooting — 水色(導入)
- 根付き木DP・部分木集約 — 水色。概念上の親: 木DP・集約・rerooting
- rerooting・全方位木DP — 青色。概念上の親: 木DP・集約・rerooting
- 木のancestor・部分木・pathを索引化する — 水色(導入)
- Euler順による部分木区間化 — 水色。概念上の親: 木のancestor・部分木・pathを索引化する
- ancestor query・LCA — 水色。概念上の親: 木のancestor・部分木・pathを索引化する
- Heavy-Light Decomposition — 青色。概念上の親: 木のancestor・部分木・pathを索引化する
- virtual tree・auxiliary tree — 黄色。概念上の親: 木のancestor・部分木・pathを索引化する
- 対称性・深さ・label区間で巨大な完全二分木を数える — 水色
- laminar区間族の包含木構築 — 青色
- DSU merge tree・Kruskal reconstruction tree — 青色
- 木の均衡分離点から重心分解へ進む — 黄色
- 加法的tree metric復元 — 橙色
- 01 on Tree・親先行順序のcluster縮約 — 橙色
- heavy path上の多項式木DP — 橙色
- rake・compressで動的木DPを保つ — 橙色
- 資源DPを引数で渡すHLRecDP — 赤色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC220 E「Distance on Large Perfect Binary Tree」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 対称性・深さ・label区間で巨大な完全二分木を数える(同じ深さの対称性と2冪で距離splitを集約するか、heap番号の祖先case分解と子孫label区間を使い、巨大な完全二分木を展開せず数えられる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 暗黙・対称な完全二分木の深さ算術、法上の四則演算・高速累乗・逆元
- ABC246 G「Game on Tree 3」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: 単調境界探索 / 補助タグ: 根付き木DP・部分木集約
- ABC293 Ex「Optimal Path Decomposition」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: 単調境界探索 / 補助タグ: 根付き木DP・部分木集約
- ABC362 F「Perfect Matching on a Tree」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 木の均衡分離点から重心分解へ進む(非負頂点重みの総和に対し、除去後の各成分を半分以下にする一点を線形時間で選び、通常の頂点数重心と葉数重心を区別できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 構成解・witness復元、木の均衡分離点と重心分解
- ABC369 G「As far as possible」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 根付き木DP・部分木集約
- ABC387 F「Count Arrays」 公式問題
技能・出典
主題: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。 cycle縮約後の木でdp[v][j]=∏_{子u}Σ_{k≤j}dp[u][k]。子ごとにprefix和を作れば、親の値ごとに子の全値を走査する二乗因子が消える。functional graph縮約と木DPを先に履修する。主タグ: 関数グラフのcycle・tree分解 / 補助タグ: DP遷移の集約・高速化、根付き木DP・部分木集約
- ABC424 E「Cut in Half」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 対称性・深さ・label区間で巨大な完全二分木を数える(同じ深さの対称性と2冪で距離splitを集約するか、heap番号の祖先case分解と子孫label区間を使い、巨大な完全二分木を展開せず数えられる。)。主タグ: 単調境界探索 / 補助タグ: 暗黙・対称な完全二分木の深さ算術
- ABC435 F「Cat exercise」 公式問題
技能・出典
主題: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。) / 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: Cartesian treeによる区間極値分解 / 補助タグ: DPの最小十分状態、単調stack・queueによる支配候補の削除、根付き木DP・部分木集約
- ABC438 F「Sum of Mex」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 根付き木DP・部分木集約、ancestor query・LCA
- ABC453 F「Avoid Division」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 木の均衡分離点から重心分解へ進む(非負頂点重みの総和に対し、除去後の各成分を半分以下にする一点を線形時間で選び、通常の頂点数重心と葉数重心を区別できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 N=2を別扱いし、元の木の葉に重み1、他に0を置いて一点だけ均衡分離点を選ぶ。各成分の葉数が全葉数の半分以下になることを使い、残数最大の異なるgroupへ色を配る。削除後に生じた葉を数え直したり、各成分を再帰的に重心分解したりしない。主タグ: 構成解・witness復元 / 補助タグ: 貪欲法と交換論、木の均衡分離点と重心分解
- ABC460 F「Farthest Pair Query」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。) / 基準点からの木距離・剰余類・直径・中心(一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。)。主タグ: 区間monoid要約 / 補助タグ: ancestor query・LCA、木距離・直径・中心・最遠点
前提・学習成果・出典
導入対象の目安: 水色(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では扱わないもの
- なし