HL分解 Heavy-Light Decomposition 木に対するクエリをO(log^2n)くらいで処理できる 辺にコストが載っている場合は頂点にコストを移す 部分木クエリもこなせる構築方法 問題 頂点にコストがある問題 yukicoder No.399 動的な領主 HL分解 + 遅延セグ木(区間加…

オイラーツアー 木をDFSしたときの順番で頂点を記録する手法 pre-order : 頂点に到着したら記録 post-order : 頂点から離れるときに記録 用途 根付き木のある頂点からの部分木に対するクエリを処理 ある頂点がある頂点の部分木に含まれるかを高速に判定する …