StaticTopTree

クラス · Static Top Tree（木を rake / compress の二分木へ分解する）

struct StaticTopTree;

概要

Static Top Tree（木を rake / compress の二分木へ分解する）

木を HL 分解し、heavy path 上のクラスタを compress で連結、頂点にぶら下がる軽辺部分木を重み二分の rake で束ねることで、高さ $O(\log n)$ の二分木を作る。この形状に StaticTopTreeDP を載せると、頂点値の点更新を $O(\log n)$ で反映しながら木 DP の値を保てる。

分解結果はグラフ表現に依存しないので構築だけを graph_type でテンプレート化している。ノード番号 $[0, n)$ は元の頂点番号（Type::Vertex のノード）と一致し、子の番号は必ず親より小さい（番号の昇順がボトムアップ順になる）。

計算量

構築は $O(n)$、ノード参照は $O(1)$

備考

非連結なグラフを渡した場合、根 r を含む連結成分だけが分解される。

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空のStatic Top Treeを構築する (2) 木gを根rからStatic Top Treeへ分解する	(1) $O(1)$ (2) $O(n)$

メンバ関数

名前	説明	計算量
`size`	元の木の頂点数を返す（Top Tree のノード数は `nodes.size()`）	$O(1)$

メンバ型

名前	説明	計算量
`Node`	Top Tree の二分木ノード	各フィールドの参照は $O(1)$

メンバ変数

名前	説明	計算量
`Type`	Top Tree ノードが表す結合操作の種類	列挙型のため実行時コストなし
`root`	Top Tree の根ノード番号。空の木では `-1`	$O(1)$ で参照可能
`nodes`	Top Tree の全ノード。先頭 $n$ 個が頂点に対応する `Type::Vertex` ノード	1 ノードの参照は $O(1)$

メンバの詳細

(constructor)

// (1)
StaticTopTree() = default;

// (2)
template <graph_type G>
explicit StaticTopTree(const G &g, int r = 0);

(1) 空のStatic Top Treeを構築する

計算量: $O(1)$

(2) 木gを根rからStatic Top Treeへ分解する

計算量: $O(n)$

Node

struct Node;

Top Tree の二分木ノード

計算量: 各フィールドの参照は $O(1)$

メンバ	説明
`p`	親・左子・右子のノード番号（存在しなければ `-1`）
`type`	このノードが表す結合操作