heavy_light_decomposition
クラス · HL分解
struct heavy_light_decomposition;
概要
HL分解
計算量
- 構築は $O(n)$、経路問合せは $O(\log n)$、部分木区間は $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空のHL分解を構築する (2) 木gを根rとしてHL分解する (3) internal CSR木を根rとしてHL分解する |
(1) $O(1)$ (2) $O(n)$ (3) $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
size |
頂点数を返す | $O(1)$ |
get |
頂点vのHL順indexを返す | $O(1)$ |
get_parent |
頂点vの親を返す | $O(1)$ |
get_depth |
頂点vの深さを返す | $O(1)$ |
dist |
u-v間の辺数を返す | $O(\log n)$ |
jump |
uからvへk辺進んだ頂点を返し、経路より長ければ-1を返す | $O(\log n)$ |
la |
vのk個上の祖先を返す | $O(\log n)$ |
lca |
uとvのLCAを返す | $O(\log n)$ |
for_each |
u-v頂点経路をHL順の半開区間へ分割してfへ渡す | callback呼出し $O(\log n)$ 回 |
for_each_edge |
u-v辺経路をHL順の半開区間へ分割してfへ渡す | callback呼出し $O(\log n)$ 回 |
for_subtree |
頂点vの部分木に対応するHL順区間をfへ渡す | $O(1)$ |
subtree |
頂点vの部分木に対応するHL順区間を返す | $O(1)$ |
for_subtree_edge |
頂点vの部分木辺に対応するHL順区間をfへ渡す | $O(1)$ |
メンバの詳細
(constructor)
// (1)
heavy_light_decomposition() = default;
// (2)
template <graph_type G>
heavy_light_decomposition(const G &g, int r = 0);
// (3)
heavy_light_decomposition(const internal::Csr<int> &g, int r = 0);
(1) 空のHL分解を構築する
- 計算量: $O(1)$
(2) 木gを根rとしてHL分解する
- 計算量: $O(n)$
(3) internal CSR木を根rとしてHL分解する
- 計算量: $O(n)$