はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるHL分解まとめ

HL分解

問題

頂点にコストがある問題

辺にコストがある問題

未整理
CodeChef Idols and Fans

【発展的話題】【工事中】HL分解の頂点の列は適切に配置すればオイラーツアーのそれと同じになる

つまり、二点間のパスに対して以外にも同じデータ構造で部分木に対してもクエリ操作が行えるということ。
こういう問題とか
こういう問題とか 解説
逆にオイラ―ツアーだけでHL分解の代用もできる?
「HL分解でやるものは逆演算が定義できそうな感じのものはだいたいEulerTour+segtreeでできる」という話もある。