HL分解で解ける問題を最近よく見る。（想定解法であるかどうかは別として）

No.235 めぐるはめぐる (5) - yukicoder
F: 根付き木のみさわさん - 天下一プログラマーコンテスト2015本戦（オープンコンテスト） | AtCoder
Problem - 588E - Codeforces
Problem - 593D - Codeforces

HL分解については、この記事がとてもわかりやすい。math314.hateblo.jp

HL分解については既に分かりやすい記事があるので、この記事では木をパスに分解してクエリするという考え方について説明する。

たとえば、パス上の値の総和を求めるというものを考える。

今回のクエリの答えは2+3+4+9+6+4+7+5=40。

一次元であればSegment TreeやBITなどで計算できる。実は木をパスに分解することにより、このようなクエリに対してもSegment TreeやBITを使うことができる。

まず木をパスに分解するというのは、こんな感じのイメージ。

それぞれのパスに対して、根に近い方から順に番号を割り振っていく。ついでにパスにも番号を振っておく。

最初の例のクエリはこんな感じだった。

このクエリを計算するには
path 0: [0,1]
path 1: [0,1]
path 3: [0,0]
path 4: [0,1]
path 5: [0,0]
に対するクエリをそれぞれ計算してマージすればいいことがわかる。たとえば総和クエリだったら、それぞれのパスのクエリ結果を計算して足すだけである。

さてここで問題になるのはu-vパスクエリを計算するときに必要になるパスの数だ。実はパスの分解方法にHL分解を使うと必要な数がO(log n)になる。つまりSegmentTreeを用いれば、クエリ一回あたりO(log^2 n)で計算できる。

実装するときはLCA(u,v)を含むパス以外はすべて[0,x]という形のクエリになっていることを意識するとやりやすい。ライブラリ化してしまえばSegment Treeの問題を解くのと大差なくなる。