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<F>(&self, x: usize, y: usize, f: F)

where F: FnMut(usize, usize),

頂点xから頂点yへ向かうパス上の頂点についてのクエリを扱う。

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

Time complexity $O(\log n)$

pub fn path_query_vertex_non_commutative<LFunc, RFunc>( &self, x: usize, y: usize, f: LFunc, g: RFunc, )

where LFunc: FnMut(usize, usize), RFunc: FnMut(usize, usize),

頂点xから頂点yへ向かうパス上の頂点についてのクエリを扱う。

Time complexity $O(\log n)$

pub fn path_query_edge<F>(&self, x: usize, y: usize, f: F)

where F: FnMut(usize, usize),

頂点xから頂点yへ向かうパス上の辺についてのクエリを扱う。

Time complexity $O(\log n)$

pub fn subtree_query_vertex<F>(&self, x: usize, f: F)

where F: FnOnce(usize, usize),

頂点xの部分木の頂点についてのクエリを扱う。

Time complexity $O(1)$

pub fn subtree_query_edge<F>(&self, x: usize, f: F)

where F: FnOnce(usize, usize),

頂点xの部分木の辺についてのクエリを扱う。

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.