HL分解 メモ

HL分解とは?

いくつかの頂点を一つの頂点に圧縮し、部分木を全て、深さの最大値がlog(頂点数)であるようなパスグラフにする

 

何ができる?

木に対するパスクエリを高速に処理できるようになる

 

実装

1.適当な根を定め、各頂点に対し部分木のサイズを求める

2.各頂点に対して、一番部分木のサイズが大きい子を一つ求める(この子との間の辺をheavyな辺、そうでない辺をlightな辺とする)

3.heavyな辺をつないでできるパスを一つの頂点に圧縮する(同じラベルを貼る)

4.元のグラフの各頂点に対し、圧縮後の頂点番号と、圧縮後の親の頂点番号を記録する

 

 

参考文献

https://math314.hateblo.jp/entry/2014/06/24/220107#fn-ee97d7f1

https://lumakernel.github.io/ecasdqina/graph/HL-Decomposition

https://ei1333.github.io/luzhiled/snippets/tree/heavy-light-decomposition.html

https://codeforces.com/blog/entry/12239