Struct HLD

pub struct HLD { /* private fields */ }

重軽分解

Implementations

impl HLD

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

Time complexity $O(n)$

Space complexity $O(n)$

pub fn path_query_vertex(&self, x: usize, y: usize) -> Vec<(usize, usize)>

演算は可換性を仮定する。

Time complexity $O(\log n)$

pub fn path_query_edge(&self, x: usize, y: usize) -> Vec<(usize, usize)>

Time complexity $O(\log n)$

pub fn subtree_query_vertex(&self, x: usize) -> (usize, usize)

Time complexity $O(1)$

pub fn subtree_query_edge(&self, x: usize) -> (usize, usize)

Time complexity $O(1)$

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

Time complexity $O(1)$

pub fn get_id(&self, x: usize) -> usize

Time complexity $O(1)$

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

Time complexity $O(1)$

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

Time complexity $O(\log n)$

Trait Implementations

impl Clone for HLD

fn clone(&self) -> HLD

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for HLD

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.