Function auxiliary_tree 

pub fn auxiliary_tree(
    nodes: &[usize],
    inv_ord: &[usize],
    lca: &LowestCommonAncestor,
) -> (usize, HashMap<usize, Vec<usize>>)

auxiliary tree です。

計算量

hash map のコストは無視する。

グラフの頂点数を n, nodes.len() を k として、O(klogn + klogk)

引数

• nodes： {0, 1, …, n - 1} の部分集合
• inv_ord: pre-order (行きがけ順) の列の添字と値を反対にしたもの
  • 頂点 i は行きがけ順で inv_ord[i] 番目に現われる
• lca: 2頂点の LCA を得る .get(u, v) を実装した構造体

返り値

(root, g)

• g.contains_key(&i): 頂点 i が圧縮後の木に含まれて、子のリストが g[&i] である
• !g.contains_key(&i): 頂点 i が圧縮後の木に含まれない