Struct LinkCutTree

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

Link-Cut Tree

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

Implementations

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

pub fn new_commutative(monoid: M, n: usize) -> Self

可換モノイドを持てるLinkCutTree<M>を生成する。

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

pub fn new_non_commutative(monoid: M, n: usize) -> Self

非可換なモノイドを持てるLinkCutTree<M>を生成する。

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

where M::Element: Clone,

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::Element)

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

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

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

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

頂点kの値を返す。

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

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

Panics

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