読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

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

HL分解

  • Heavy-Light Decomposition
  • 木に対するクエリをO(log^2n)くらいで処理できる
  • 頂点にコストが載っているときと辺にコストが載っているときで処理が違ってくる
  • 辺にコストが載っている場合は以下のようにして頂点にコストを移す

http://pekempey.hatenablog.com/entry/2015/11/05/210543

以下、問題




頂点にコストがある問題

yukicoder No.399 動的な領主
HL分解 + 遅延セグ木(区間加算 + 区間総和)
yukicoder No.235 めぐるはめぐる(5)
HL分解 + 遅延セグ木(区間加算 + 区間総和)

辺にコストがある問題

[http://www.spoj.com/problems/QTREE/:title=
SPOJ QTREE - Query on a tree]
HL分解 + セグ木(区間max)
Codeforces #329 Div2 D. Happy Tree Party
HL分解 + セグ木(区間積)