DSU merge tree・Kruskal reconstruction tree
概要
成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。
考え方
成分併合のたび新しい内部頂点を作り、併合前の二成分を子にする。DSUの親を履歴として使わず、併合が起きた閾値や時刻を木へ保存する。
初期要素を木の葉0,…,N−1とし、DSU各根にその成分の木rootを保存する。異根a,bを併合するeventでは新nodezを作り、children[z]=(treeRoot[a],treeRoot[b])、label[z]=event時刻または重みとし、DSU併合後の根へtreeRoot=zを保存する。同根eventではnodeを作らない。
二葉u,vが初めて同じ成分になるeventがちょうどLCA(u,v)なので、label[LCA]が接続時刻・minimax閾値になる。時刻Tの成分サイズは、葉からlabel≤Tの祖先を最大限上がり、その部分木葉数を読む。非連結の森には別成分を識別する印を付け、同重みの複数併合nodeは同じlabelなのでサイズqueryでもその同値群を全部上がる。
成立条件と計算量
N要素なら併合頂点は高々N−1。構築はDSUの費用、LCA索引はO(N log N)。二点が同じ成分になった時刻はLCAの属性から読める。併合しないeventと非連結の最終森を区別する。
問題一覧
- ABC314 F「A Certain Game」 公式問題
技能・出典
主題: DSU merge tree・Kruskal reconstruction tree(成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: DSU merge tree・Kruskal reconstruction tree / 補助タグ: 寄与の数え上げと順序交換、DSUによる連結成分管理・縮約、法上の四則演算・高速累乗・逆元、根付き木DP・部分木集約
- ABC235 Ex「Painting Weighted Graph」 公式問題
技能・出典
主題: DSU merge tree・Kruskal reconstruction tree(成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。主タグ: DSU merge tree・Kruskal reconstruction tree、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。DSUの併合履歴を木に保存し、時刻や閾値のqueryを祖先関係へ写す。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 木構造。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dsu-merge-tree
DSU merge tree・Kruskal reconstruction tree
習得する技能
- 成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: DSUによる連結成分管理・縮約。
このUnitを直接前提とする単元: なし。
DSUによる連結成分管理・縮約で得た考え方と実装を再利用し、DSU merge tree・Kruskal reconstruction treeの発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- DSU merge tree・Kruskal reconstruction treeの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。