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の親の規約を固定する。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 水色(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順による部分木区間化の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠