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と非連結の最終森を区別する。

問題一覧

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

前提・学習成果・出典

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

根拠