Euler順による部分木区間化
概要
DFS入退時刻で各部分木を連続区間へ写し、配列上の更新・集約へ変換する。
考え方
DFSで入った時刻tinを付け、部分木の処理が終わる時刻toutを保存する。vの部分木は[tin[v],tout[v])になるため、部分木集約を配列区間queryへ移せる。
時計timer=0から、DFS入場でtin[v]=timer++を記録し、全子の処理後にtout[v]=timerとする。出場時には時計を増やさない。祖先uの部分木内で全子を処理し終えるまで外へ出ないため、子孫はちょうど[tin[u],tout[u])へ入る。
頂点uの寄与を、uを含む根→v path全てへ加える場合、対象vはuの子孫なので同じ部分木区間へ加算する。区間加算・一点取得の配列表現で各vの根path和を保てる。逆に部分木の点値を集約するなら、a[tin[v]]=value[v]として区間和を取る。何を点へ置き何を区間へ作用させるかを区別する。
成立条件と計算量
前処理O(N)、以後はFenwick TreeやSegment Treeの費用。入場時一回の列と、LCA用に出場も記録するEuler tourは長さと意味が違う。祖先判定は区間包含で行い、rootの親の規約を固定する。
問題一覧
- ABC240 E「Ranges on Tree」 公式問題組合せ: 成立証明から構成解を復元する
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。既習技能: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: Euler順による部分木区間化 / 補助タグ: 構成解・witness復元
- ABC406 F「Compare Tree Weights」 公式問題
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: Euler順による部分木区間化 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC294 G「Distance Queries on a Tree」 公式問題
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。追加で学ぶ技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: ancestor query・LCA、Euler順による部分木区間化 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC337 G「Tree Inversion」 公式問題
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: Euler順による部分木区間化 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。DFS時刻で部分木が連続区間になることを使い、区間queryへ写す。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 木のancestor・部分木・pathを索引化する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-tree-euler-flattening
Euler順による部分木区間化
習得する技能
- Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: Heavy-Light Decomposition、virtual tree・auxiliary tree。
DFS入退時刻で各部分木を連続区間へ写し、配列上の更新・集約へ変換する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- Euler順による部分木区間化の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。