Struct LCA

pub struct LCA { /* private fields */ }

LCA

• 最小共通祖先を求めるクエリに答える

Implementations

impl LCA

pub fn new(tree: &Vec<Vec<usize>>, root: usize) -> Self

rootを根に持つ木treeで、初期化を行う

pub fn depth(&self, v: usize) -> usize

頂点 v の深さを求める

pub fn parent(&self, v: usize) -> Option<usize>

頂点 v の親を求める

pub fn lca(&self, u: usize, v: usize) -> usize

頂点 u,v の最小共通祖先を求める

pub fn dist(&self, u: usize, v: usize) -> usize

頂点 u,v の距離を求める

pub fn kth_ancestor(&self, v: usize, k: usize) -> Option<usize>

頂点 v の k 個上の祖先を求める

pub fn kth_on_path(&self, u: usize, v: usize, k: usize) -> Option<usize>

頂点 u から v へ向かうパス上の k 個目の頂点を求める