Heavy-Light Decomposition
最近アツイ*1、木を分解する手法の一つ。 重軽分解 とか、HL-decompositionとか呼ばれている。
アルゴリズム
- edgeを"Heavy"と"Light"に分けて
- "Heavy"edgeで繋がれた頂点を一つにまとめる
の2段構成。
ここに書いてあるedgeの分け方は元のHeavy Light Decompositionと違うかも
edgeの分け方
以下、根付き木について考える。
頂点vの子供u1,u2 ... ux とのedge ei = <v,ui> について、
- 子の中で、最も部分木のサイズが大きい頂点 uk を選び、 ek = <v,uk> を "Heavy"とする
- 複数ある場合、どれを選んでもよい
- それ以外は "Light"
と分ける。*2
図で表すと、以下のように部分木のサイズを計算して…
こんな感じに"Heavy"と"Light"に分ける。
そして、"Heavy"edgeで繋がれた頂点を一つにまとめると、こうなる。
すると、
- 各頂点から出る辺について、"Heavy"になる本数は最大1本
- "Heavy"edgeで繋がれた頂点を一つにまとめ、それらを元の"Light"edgeで繋げたグラフを考えると、 あらゆる頂点の深さが高々O(log n)になる
- 一つにまとめられた頂点群は、分岐のないパスになる
という条件が成り立つ。
a)
定義により明らか
b)
| "Light"で結ばれている子供の部分木のサイズ | <= |親のサイズ| / 2 であるから、
"Light"で結ばれた子を辿っていくと、部分木のサイズが半分以下、半分以下と指数的に小さくなる。
よって分解後のグラフの深さは、最大で floor(log(n)) + 1、つまり O(log n)
c)
同じ高さの頂点が分解した部分木に含まれていないことと同値である。
同じ高さの頂点u,vが部分木に含まれていると仮定すると、u,vのLCA(Lowest common ancestor | ふたつの頂点の共通祖先の中で、最も深い頂点) pについて、pからu,pからvにそれぞれ"Heavy"edgeが伸びている事になる。
これは A) に反するので矛盾、つまり、一つにまとめられた頂点群は、根からの深さが1刻みの一直線のパスになる。
利点
- あるnodeからrootまでのクエリの処理を高速に行える形に分解出来る
- b) より、あるnodeからrootの間で通過する部分木の個数はO(log n)
- c) より、各部分木は、配列に用いるデータ構造が使える
- segment tree
- BIT etc...
- さっきから使ってる図を使うとこんな感じ
- 木におけるnode間のクエリは、大体複数の node <-> root のクエリに置き換える事が出来るので、こちらも高速に解ける
欠点
- 単体ではそれほど実装は重くないが、LCAやsegment treeと使うので全体としてみると重い
問題
- Housewife Wind - http://poj.org/problem?id=2763
- Idols and Fans - http://www.codechef.com/problems/IDOLS
- 想定解法がHL-decomposition + segment tree
- http://www.codechef.com/viewsolution/4134274
- The L-th Number - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270
- 非想定解なので、TLEがこわいが通った
- HL-decomposition + 要素にsort済の配列を持つsegment tree(range treeの一種)
- http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=995498&tab=1
- 想定解は永続データ構造
