link cut tree

個人的メモ

(注1) link の実装はどちらの頂点も木の根でない場合に対応するために access ではなく evert にしている. 親子関係を意識しないような動的森の管理に適していて, またそのようなときに cut を行う場合は cut(u, v) を用いると良い.
(注2) link の実装において u->par = v の前に access(v) を加えた方が下記の計算量解析のポテンシャルの取り方の意味では正しいが、 結局 $u$ を根とする部分木内の頂点に初めて access を行なった場合にポテンシャルの偏りが解消されるので(ただ遅延しているだけなので)ポテンシャルの取り方を適当に変えてあげれば計算量を保障できる.
(注3) 以下はパス上の加算・総和のクエリだが適宜他の演算に変更可. ただし演算が非可換である場合は少し気をつけて実装する必要がある.
(雑なメモ) Splay Tree について
(追記)
この講義 およびその Lecture note を参考にしました.
結局 access$(v)$ がならし $\O (\log n)$ であることを示せば十分である. つまり splay 木を回転する回数が各 access$(v)$ でならし $\O (\log n)$ となることを示す.
まず splay 木がならし $\O (\log n)$ になる理由(Access Lemma) を用います. 具体的には "頂点 $u$ を根とする splay 木に含まれる頂点 $v$ に対して splay$(v)$ を行なったときのならしコストが $3( \mathrm{rank} (u) - \mathrm{rank} (v)) + 1$ で抑えられる" である.
link cut tree においてはこの $\mathrm{rank} (x)$ を次のように定める. $x$ の属する splay 木を $T(x)$, その splay 木内において $x$ を根とする部分木を $T'(x)$ とする. このとき $\mathrm{rank}(x) = \log ( |T'(x)| + $($y \in T'(x)$, $y$ の non-preferred child $z$ について $\mathrm{rank} (z)$ の和) ) とする. つまり $x$ を含む splay 木に限らず, $x$ 以下にあるすべての頂点の数の合計の $\log$ とする. そしてポテンシャルはもちろん $\sum_{x} \mathrm{rank}(x)$ である.
すると access$(v)$ で splay 操作にかかる総ならしコストは $3(\mathrm{rank}(root) - \mathrm{rank}(v)) + $(preferred child の変化する回数) で抑えられることがわかる. splay 操作をする回数は preferred child の変化する回数で抑えられることに注意する. また preferred child の変化に伴って, 頂点の $\mathrm{rank}$ が変化することがないことも確認する.
全 $m(\ge n)$ 回の access$(v)$ の操作について $3(\mathrm{rank}(root) - \mathrm{rank}(v))$ の和は $0 \le \mathrm{rank}(v) \le \log n$ より $\O (m \log n)$ となり, この部分はならし $\O (\log n)$ である. よって後は (preferred child の変化する回数), つまり (non-preferred である辺が preferred になる回数) がならし $\O (\log n)$ であることを示せばよい.
ここで元の木について edge を heavy edge, light edge の $2$ 種類に分類する. $e = (u, v)$ が heavy とは $u$ が $v$ の親であるとした場合 ($u$ を根とする部分木のサイズ) $\le 2 \times$($v$ を根とする部分木のサイズ) となるもののことをいうとする. 結果的に今 edge は heavy / light, preferred / non-preferred の $2 \times 2 = 4$ 種類あることになり, また heavy, light については常に変化しないことに注意する.
$1$ 回の access$(v)$ で light かつ non-preferred な辺が preferred になる回数は根からのパス上に light edge は高々 $\lceil \log n \rceil$ 個以下しかないことから $\lceil \log n\rceil$ 個で抑えられるので, heavy かつ non-preferred な辺が preferred になる回数を考える. そこで $1$ 回の access$(v)$ で heavy かつ preferred な辺が preferred から non-preferred になる回数を考えると, これは同じタイミングで light edge が non-preferred から preferred になるので $\lceil \log n\rceil$ 回で抑えられる. ゆえに (heavy かつ non-preferred な辺が preferred になる回数) $\le$ (初めの段階で heavy かつ non-preferred な辺の個数) + (heavy かつ preferred な辺が preferred から non-preferred になる回数) であることを考えると 全 $m(\ge n)$ 回の access$(v)$ の操作で (heavy かつ non-preferred な辺が preferred になる回数) は $\O (m \log n)$ 回となり, $1$ 回の access$(v)$ ではならし $\O (\log n)$ 回であることが分かる. ゆえにすべて示せた.

結論: link cut tree はマジで天才.