DynamicTopTree

クラス · Dynamic Top Tree（Link/Cut/Evert に対応した全方位木 DP）

template <class TreeDP>
struct DynamicTopTree;

概要

Dynamic Top Tree（Link/Cut/Evert に対応した全方位木 DP）

LCT の compress パス（splay 木）に加え、各頂点にぶら下がる軽辺（rake 対象の部分木）を別の splay 木で束ねて expose のたびに $O(\log n)$ 償却で繋ぎ替える。evert によるパス反転に対応するため、パス集約を正方向 sum・逆方向 mus の 2 本立てで保持する（compress が非可換なため、反転を高速に行うにはこの複製が必要）。 TreeDP のインターフェースは StaticTopTreeDP（tree_dp concept）と共通： Path vertex(int u) / Path add_vertex(Path d, Light l) / Light add_edge(Path d) / Light rake(Light l, Light r) / Path compress(Path p, Path c)。

計算量

構築は $O(n)$、各動的木操作は償却 $O(\log n)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空のDynamic Top Treeを構築する (2) n個の孤立頂点とTreeDPを構築する	(1) $O(1)$ (2) $O(n)$

メンバ関数

名前	説明	計算量
`link`	c を子、p を親として連結する（内部で c を自身の根に evert してから繋ぐ）	償却 $O(\log n)$
`cut`	(1) c を親から切り離す (2) 辺 (u, v) を切り離す	償却 $O(\log n)$
`evert`	u を全体の根にする	償却 $O(\log n)$
`update`	頂点 u の情報が変化した後に呼び、集約を再計算する	償却 $O(\log n)$
`query`	u を根としたときの木全体の集約値	償却 $O(\log n)$
`query_subtree`	root を根としたときの、u を根とする部分木の集約値	償却 $O(\log n)$

メンバ型

名前	説明	計算量
`Path`	path clusterの集約型	型エイリアスで実行時計算量はない
`Light`	light edge clusterの集約型	型エイリアスで実行時計算量はない

メンバの詳細

(constructor)

// (1)
DynamicTopTree() = default;

// (2)
explicit DynamicTopTree(int n, const TreeDP &_dp = TreeDP());

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

計算量: $O(1)$

(2) n個の孤立頂点とTreeDPを構築する

計算量: $O(n)$

cut

// (1)
void cut(int c);

// (2)
void cut(int u, int v);

(1) c を親から切り離す

計算量: 償却 $O(\log n)$

(2) 辺 (u, v) を切り離す

計算量: 償却 $O(\log n)$