Struct HLD

pub struct HLD {
    pub N: usize,
    pub root: usize,
    pub G: Vec<Vec<usize>>,
    pub parent: Vec<usize>,
    pub subtree_size: Vec<usize>,
    pub in_: Vec<usize>,
    pub out: Vec<usize>,
    pub head: Vec<usize>,
}

HL分解

Fields

N: usize

頂点数

root: usize

根

G: Vec<Vec<usize>>

グラフ

parent: Vec<usize>

親頂点

subtree_size: Vec<usize>

subtree_size[i] := iを根とする部分木のサイズ

in_: Vec<usize>

行きがけ順での番号

out: Vec<usize>

帰りがけ順での番号

head: Vec<usize>

heavy pathの端点

Implementations

impl HLD

pub fn new(N: usize) -> Self

N頂点の木を初期化する

pub fn add_edge(&mut self, u: usize, v: usize)

辺(u,v)を追加する

pub fn decompose(&mut self, root: usize)

頂点rootを根としてHL分解をする

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

頂点vの配列上でのインデックス

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

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

pub fn get_subtree<T, F>(&self, u: usize) -> (usize, usize)

uを根とする部分木の値を集約する

（モノイドMが可環であるときに定義される）

戻り値

• (usize, usize) : (左, 右)

pub fn get_path(&self, u: usize, v: usize) -> PathSegment<'_>

頂点u,v間のパス上のパス断片を順に返すイテレータを返す．

戻り値 (Item)

• i (usize) : 最も根側の頂点
• j (usize) : 最も葉側の頂点
• last (bool) : 最後のpath segmentであるか
• rev (bool) : 取得するpathの向きに対してpath segmentが逆方向かどうか