link_cut_tree
クラス · Link-Cut Tree
template <monoid M>
struct link_cut_tree;
概要
Link-Cut Tree
計算量
- 構築は $O(n)$、link・cut・reroot・exposeは償却 $O(\log n)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) n個の単位元頂点を構築する (2) 頂点値vから構築する |
$O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
set |
頂点vの値をvalへ変更する | 償却 $O(\log n)$ |
get_value |
頂点v自身の値を返す | $O(1)$ |
get_total |
現在の補助木でv以下の集約値を返す | $O(1)$ |
link |
uとvを連結する | 償却 $O(\log n)$ |
cut |
(1) 辺u-vを切断する (2) vを親から切断する |
償却 $O(\log n)$ |
splay |
vを補助木の根までsplayする | 償却 $O(\log n)$ |
make_root |
vを表現木の根にする | 償却 $O(\log n)$ |
expose |
根からvまでのpreferred pathを露出する | 償却 $O(\log n)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
node_type |
内部ノード型 | 型エイリアスで実行時計算量はない |
node_ptr |
内部ノードへのpointer型 | 型エイリアスで実行時計算量はない |
メンバの詳細
(constructor)
// (1)
link_cut_tree(int n);
// (2)
link_cut_tree(const std::vector<T> &v);
(1) n個の単位元頂点を構築する
- 計算量: $O(n)$
(2) 頂点値vから構築する
- 計算量: $O(n)$
cut
// (1)
void cut(int u, int v);
// (2)
void cut(int v);
(1) 辺u-vを切断する
- 計算量: 償却 $O(\log n)$
(2) vを親から切断する
- 計算量: 償却 $O(\log n)$