math314のブログ

主に競技プログラミング,CTFの結果を載せます

Heavy-Light Decomposition

最近アツイ*1、木を分解する手法の一つ。 重軽分解 とか、HL-decompositionとか呼ばれている。

アルゴリズム

  1. edgeを"Heavy"と"Light"に分けて
  2. "Heavy"edgeで繋がれた頂点を一つにまとめる

の2段構成。

ここに書いてあるedgeの分け方は元のHeavy Light Decompositionと違うかも

edgeの分け方

以下、根付き木について考える。

f:id:math314:20140624214632p:plain

頂点vの子供u1,u2 ... ux とのedge ei = <v,ui> について、

  • 子の中で、最も部分木のサイズが大きい頂点 uk を選び、 ek = <v,uk> を "Heavy"とする
    • 複数ある場合、どれを選んでもよい
  • それ以外は "Light"

と分ける。*2

図で表すと、以下のように部分木のサイズを計算して…

f:id:math314:20140624214848p:plain

こんな感じに"Heavy"と"Light"に分ける。

f:id:math314:20140624214909p:plain

そして、"Heavy"edgeで繋がれた頂点を一つにまとめると、こうなる。

f:id:math314:20140624215235p:plain

すると、

  1. 各頂点から出る辺について、"Heavy"になる本数は最大1本
  2. "Heavy"edgeで繋がれた頂点を一つにまとめ、それらを元の"Light"edgeで繋げたグラフを考えると、 あらゆる頂点の深さが高々O(log n)になる
  3. 一つにまとめられた頂点群は、分岐のないパスになる

という条件が成り立つ。

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...
    • さっきから使ってる図を使うとこんな感じ

f:id:math314:20140624215540p:plain

  • 木におけるnode間のクエリは、大体複数の node <-> root のクエリに置き換える事が出来るので、こちらも高速に解ける

欠点

  • 単体ではそれほど実装は重くないが、LCAやsegment treeと使うので全体としてみると重い

問題

*1:[要出典]

*2: |子node vの部分木のサイズ| >= |親node pの部分木のサイズ| / 2 + 1 を満たす edge <p,v> を heavy path と定義するらしい? が、こう定義しても競技プログラミングで欲しい性質を満たす && 速そう