Struct LinkCutTree

pub struct LinkCutTree<M: Monoid> { /* private fields */ }

Link-Cut Tree

動的に木の辺を追加・削除可能

Implementations

impl<M: Monoid + Clone> LinkCutTree<M>

pub fn new(n: usize) -> Self

LinkCutTree<M>を生成する。

pub fn expose(&mut self, k: usize)

pub fn cut(&mut self, i: usize, j: usize)

頂点iと頂点jの間にある辺を削除する。

Panics

頂点iと頂点jが隣接していないときパニックする。

pub fn link(&mut self, i: usize, j: usize)

頂点iと頂点jの間に辺を張る。

Panics

頂点iと頂点jが同一の木に属するときパニックする。

pub fn evert(&mut self, k: usize)

pub fn set(&mut self, k: usize, x: M)

頂点kの値をxに変更する。

pub fn update(&mut self, k: usize, x: M)

頂点kの値をモノイドの演算と値xで更新する。

pub fn get(&self, k: usize) -> M

頂点kの値を返す。

pub fn fold(&self, i: usize, j: usize) -> M

頂点i,j間のパス上でのモノイドの演算の結果を返す。

Panics

頂点iとjが同一の木に属していないときパニックする。