Link/Cut Tree
(tree/link_cut_tree.hpp)
Description
Link/cut tree は,森を管理するデータ構造である.以下の機能を提供する:
- 辺の追加
- 辺の削除
- 根の変更
- 頂点の値の更新
- パス上の頂点の値 (モノイド) の総和
木をパスに分解し,それぞれのパスを splay tree で管理することでこれらの操作を実現する.
空間計算量: $O(n)$
Operations
-
LinkCutTree(int n)
- 頂点数 $n$ で初期化する
- 時間計算量: $O(n)$
-
void link(int u, int v)
- 辺 $uv$ を追加する
- 時間計算量: $\mathrm{amortized}\ O(\log n)$
-
void cut(int v)
- 頂点 $v$ とその親を結ぶ辺を削除する
- 時間計算量: $\mathrm{amortized}\ O(\log n)$
-
void evert(int v)
- 頂点 $v$ を木の根にする
- 時間計算量: $\mathrm{amortized}\ O(\log n)$
-
int par(int v)
- 頂点 $v$ の親を返す.頂点 $v$ が親ならば $-1$ を返す.
- 時間計算量: $O(1)$
-
void get(int v)
- 頂点 $v$ の値を取得する
- 時間計算量: $O(1)$
-
void set(int v, T x)
- 頂点 $v$ の値を $x$ に変更する
- 時間計算量: $\mathrm{amortized}\ O(\log n)$
-
T fold(int u, int v)
- $uv$ パス上の頂点の値を fold する
- 時間計算量: $\mathrm{amortized}\ O(\log n)$
Reference
Verified with
Code
Back to top page