Struct lowest_common_ancestor::LowestCommonAncestor

pub struct LowestCommonAncestor { /* private fields */ }

根付き木の LCA です。

Examples

use lowest_common_ancestor::LowestCommonAncestor;

// 0 -- 2 -- 4
// |    |
// 1    3

let lca = LowestCommonAncestor::new(5, 0, &[(0, 1), (0, 2), (2, 3), (2, 4)]);
assert_eq!(lca.get(0, 1), 0);
assert_eq!(lca.get(0, 4), 0);
assert_eq!(lca.get(1, 1), 1);
assert_eq!(lca.get(1, 2), 0);
assert_eq!(lca.get(2, 3), 2);
assert_eq!(lca.get(3, 4), 2);

Implementations

impl LowestCommonAncestor

pub fn new(n: usize, root: usize, edges: &[(usize, usize)]) -> Self

頂点数 n, 根 root, 木をなす無向辺の集合 edges を渡します。

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

u と v の LCA を返します。

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

u と v の距離 (頂点間にある辺の数) を返します。

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

頂点 u の深さを返します。

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

頂点 u から根の方向に k 本の辺を登って着く頂点を返します。