HL分解
- Heavy-Light Decomposition
- 木に対するクエリをO(log^2n)くらいで処理できる
- 辺にコストが載っている場合は頂点にコストを移す
- 部分木クエリもこなせる構築方法
問題
- 頂点にコストがある問題
- yukicoder No.399 動的な領主 HL分解 + 遅延セグ木(区間加算 + 区間総和)
- yukicoder No.235 めぐるはめぐる(5) HL分解 + 遅延セグ木(区間加算 + 区間総和)
- yukicoder No.529 帰省ラッシュ HL分解 + 二重辺連結成分分解 + UnionFind + セグメントツリー(RMQ)の難問
- 辺にコストがある問題
- SPOJ QTREE - Query on a tree + セグ木(区間max)
- Codeforces #329 Div2 D. Happy Tree Party + セグ木(区間積)
- CodeChef Pishty and tree + セグ木（区間xor）
- yukicoder No.650 行列木クエリ 解説
- 部分木クエリも使う問題
- 未整理
