HL分解（Heavy-Light-Decomposition）メモ

ゴール

窃盗したライブラリでABC-Gレベルを通せるようになる

内部実装を理解する

前提

木の最小共通祖先（LCA）を知っている

セグ木の気持ちを理解していて、典型問題を通せる

ステップ1_気持ちの理解

Heavy, Lightがそれぞれ何かと、分解するとどう計算量が減ってなんで嬉しいかが分かるはず。

ステップ2_ライブラリを読む

窃盗したい実装を探して、感謝の気持ちを忘れずに読む。beet-aizuさんありがとうございます。

実装と使い方を理解する。

以下、Nは頂点数。

フィールド

G ： グラフの隣接リスト。ただしbuild時にdfs_szの中で「親方向への辺は削除する」「部分木のサイズが最大の頂点が先頭要素になるようにスワップする」をしている。

vid ： 正引き。入力のvertexから配列のidxへの変換

inv ： 逆引き。配列のidxから入力のvertexへの変換

nxt ： 連結成分の根（部分木のサイズが最大の頂点）

sub ： 自身を根とする部分木のサイズ

par ： 親頂点のvertex（根の親は-1）

メソッド

void add_edge(int u, int v)：u, vの間に無向辺を張る

void build(int r = 0)：rを根としてHL分解を行う。最初のDFSで各頂点の部分木サイズを求め、次にvidを作成する

dfs_sz(int v) ：sub, parを構成しながらGを整備

dffs_hld(int v, int& pos) ：vid, inv, nxtを作成

int lca(int u, int v)：u, vの最小共通祖先をO(log N)で求める(*1)

void for_each(int u, int v, const F& f) ：u, v間の頂点属性に対するクエリfの処理をO(X log(N))でする(*2)(*3)

void for_each_edge(int u, int v, const F& f) ：u, v間の辺属性に対するクエリfの処理をO(X log(N))でする

*1 同じ連結成分ならvidが小さい方が根。異なるならnxtのparで根方向の連結成分に移る。連結成分が高々log N個なので計算量はO(log N)

*2 Xは列に対するfの計算量。例えばセグ木で区間取得するならO(log(N)log(N))

*3 f(max~の行は、「uとvが異なる連結成分なら、vの先頭からvまで」「同じ連結成分なら、uからvまで」

ステップ3_実際に使ってみる

使い方チェック

頂点に対するクエリ

セグ木に初期値をセットする際にidxをちゃんと合わせる必要があるという教訓

辺に対するクエリ

もっと解きたい場合