auxiliary_tree

struct auxiliary_tree;

概要

auxiliary tree（補助木 / virtual tree）

コンストラクタで LCA・Euler tour を前計算し、build(vs) で指定頂点集合に対する圧縮木を何度でも構築できる。$\sum |vs|$ が小さければ各 build は $O(|vs| \log N)$。

名前	説明	計算量
`(constructor)`	木gを根rとしてLCAとEuler tourを前計算する	$O(N)$

名前	説明	計算量
`build`	指定頂点集合 v に対する圧縮木を構築する。	指定頂点数を $k$ として $O(k\log k)$

名前	説明	計算量
`tree`	build が返す圧縮木。元の木の頂点番号・親・指定頂点フラグを保持する。	構築は補助木頂点数を $k$ として $O(k)$、参照は $O(1)$

struct tree : public list_graph<void>;

build が返す圧縮木。元の木の頂点番号・親・指定頂点フラグを保持する。

メンバ	説明
`tree`	元頂点列・親列・指定頂点flagから圧縮木を構築する
`get_vertex`	補助木ノード x に対応する元の木の頂点番号
`get_parent`	補助木ノード x の親ノード番号。根は -1。
`is_specified`	補助木ノード x が指定頂点（LCA で補われた頂点でない）か
`operator[]`	頂点iの隣接辺列を取得する
`begin`	頂点ごとの隣接辺列の先頭iteratorを返す
`end`	頂点ごとの隣接辺列の終端iteratorを返す
`all_edges`	全辺を平坦に走査する view
`reserve`	各頂点の隣接リストにまとめて容量を予約する
`edge_type`	このグラフが返す辺型
`size`	頂点数を返す
`edge_count`	格納された有向辺数（無向辺は 2 本としてカウントされる）
`num_edges`	辺 ID の個数（add_edge / add_edges の呼び出し回数）
`get_edge`	ID から辺を取得する（無向辺は from→to 側を返す）
`add_edge`	有向辺を追加する。重みは e のものを使い、ID は新たに振り直す。
`add_edges`	無向辺を追加する。往復 2 本（from→to, to→from）には同じ ID を振る。
`input_edge`	標準入力からm本の有向辺を追加する
`input_edges`	標準入力からm本の無向辺を追加する