Struct Hld 

pub struct Hld {
    pub parent: Vec<Option<usize>>,
    pub depth: Vec<usize>,
    pub size: Vec<usize>,
    pub head: Vec<usize>,
    pub pos: Vec<usize>,
}

Heavy-Light Decomposition over a rooted tree.

Fields

parent: Vec<Option<usize>>

Parent of each vertex in the rooted tree. None for the root.

depth: Vec<usize>

Depth of each vertex (root has depth 0).

size: Vec<usize>

Subtree size of each vertex (including itself).

head: Vec<usize>

Head of the heavy chain containing each vertex.

pos: Vec<usize>

Position of each vertex in the linearised order of chains.

Implementations

impl Hld

pub fn new(adj: &[Vec<usize>], root: usize) -> Self

Build the decomposition for the tree adj rooted at root.

adj[v] is the list of neighbours of v. The tree is assumed to be connected and undirected; edges to a vertex’s parent are filtered automatically.

Panics

Panics if root >= adj.len().

pub fn path_segments(&self, u: usize, v: usize) -> Vec<(usize, usize)>

Decompose the path between u and v into half-open segments [lo, hi) in the linearised chain order. Pass these segments to a Fenwick / segment tree built on pos to answer path queries.

Trait Implementations

impl Clone for Hld

fn clone(&self) -> Hld

Returns a duplicate 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.