ei1333's page

HL分解(Centroid-Path-Decomposition)

説明

木をHL分解する。

計算量

$O(V)$

LCA, query: $O(\log V)$

実装例

Tree-Array

上の実装では, データ構造をheavy-path 個分必要だったが, 面倒なので $1$ 個に変換してみる。定数倍は悪くなるが実装は楽になる。