木上のクエリ処理わからね〜

どれを使ってもLCAはもとまる LCAがもとまるとu-vパスの長さと、適当な頂点wがu-vパスに含まれるかがわかる

下ではクエリの形が二項演算であるとして扱ってます あと頂点に対しても辺に対しても大体同じです(根を除いて辺と頂点が1対1で対応するので)

LCA(ダブリング)

  • 部分木クエリ 厳しい
  • パスクエリ できる 逆元不要 変更クエリは無理

オイラーツアー

  • 部分木クエリ できる SegTreeと相性よし 区間変更にも対応
  • パスクエリ できる 逆元が必要 1点変更クエリに対応(区間更新は不可)

HLD

  • 部分木クエリ できる 区間変更にも対応
  • パスクエリ できる 逆元不要 区間変更に対応

 

難易度的にはダブリング<オイラーツアー<HLD<Link/Cut<Top treeらしいです

HLDを勉強するときのために問題をおいておきます

https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_E