Auxiliary Tree（Virtual Tree／仮想木）
根付き木から必要な頂点と、それらのLCAだけを取り出して圧縮木を構築します。
この構造は Auxiliary Tree、Virtual Tree、仮想木、補助木などと呼ばれます。このドキュメントでは、AtCoder公式解説で使われているAuxiliary Treeを主名称とし、既存module名との対応のためVirtual Treeを併記します。
import
import atcoder/extra/graph/virtual_tree
前処理
let vt = initVirtualTree(graph, root = 0)
graphは0-indexedの無向木です。前処理ではEuler Tour順、深さ、二分累積によるLCA情報を構築します。
buildVirtualTree
let built = vt.buildVirtualTree(keys)
keysと、それらを接続するために必要なLCAを含む圧縮木を返します。
built.root: 圧縮木の根の添字built.vertices[i]: 圧縮頂点iに対応する元の頂点built.edges:(parent, child, dist)の列built.adj[i]: 圧縮頂点iから子への辺dist: 元の木における距離
for edge in built.edges:
echo built.vertices[edge.parent],
" -> ",
built.vertices[edge.child],
" distance = ",
edge.dist
補助API
echo vt.lca(u, v)
echo vt.dist(u, v)
echo vt.isAncestor(u, v)
計算量
元の木の頂点数を (N)、指定頂点数を (K) とします。
- 前処理: (O(N\log N))
- Auxiliary Treeの構築: (O(K\log K + K\log N))
- 構築後の頂点数: (O(K))