どれを使ってもLCAはもとまる LCAがもとまるとu-vパスの長さと、適当な頂点wがu-vパスに含まれるかがわかる
下ではクエリの形が二項演算であるとして扱ってます あと頂点に対しても辺に対しても大体同じです(根を除いて辺と頂点が1対1で対応するので)
LCA(ダブリング)
- 部分木クエリ 厳しい
- パスクエリ できる 逆元不要 変更クエリは無理
オイラーツアー
HLD
難易度的にはダブリング<オイラーツアー<HLD<Link/Cut<Top treeらしいです
HLDを勉強するときのために問題をおいておきます
https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_E