Struct DoublingLCA

pub struct DoublingLCA { /* private fields */ }

ダブリングによる最小共通祖先

Implementations

impl DoublingLCA

pub fn new<E: TreeEdgeTrait>(tree: &Tree<E>, root: usize) -> Self

Time complexity $O(n \log n)$

Space complexity $O(n \log n)$

pub fn ancestor(&self, a: usize, n: usize) -> Option<usize>

aのn個上の祖先を求める。

Time complexity $O(\log n)$

pub fn lca(&self, a: usize, b: usize) -> usize

aとbの最小共通祖先を求める。

Time complexity $O(\log n)$

pub fn jump(&self, s: usize, t: usize, d: usize) -> Option<usize>

s-t最短パス上で、sから見てd番目の頂点を返す。

Time complexity $O(\log n)$