Auxiliary Tree, Virtual Tree
概要
\(N\) 個の頂点を含む根付き木 \(T\) より、とある頂点集合 \(X = {v_1, v_2, ..., v_K}\) と それらのLCAを含むような木を構築する。
頂点集合 \(X\) に対し、以下の手順によって構築できる。
-
頂点集合 \(X\) を、グラフ \(G\) をDFSした時のpre-orderの順序で並べる
-
このリストを \(A = v_{i_1}, v_{i_2}, ..., v_{i_K}\) とする
-
-
\(1 \le j < K\) に対し、 \(w = lca(v_{i_j}, v_{i_{j+1}})\) を求める
-
頂点集合 \(X\) と(2)のlcaの頂点から、Auxiliary Treeを構築する
ここでは、具体的に以下で構築する
-
(2)において、各 \(1 \le j < K\) に対し求めたlca \(w\) をリスト \(A\) に追加する
-
リスト \(A\) に含まれる頂点をもう一度pre-orderの順序で並べる
-
リスト \(A\) に含まれる頂点 \(v_i\) を走査しながら、stackを用いてリスト \(A\) に含まれる直近の祖先 \(v_j\) を求める
頂点集合 \(X\) のサイズを \(K\) とすると、このAuxiliary Treeの頂点数は高々 \(2K-1\) になる。
計算量
Euler Tour TechniqueとSparse Tableを用いた場合
-
前計算: \(O(N \log N)\)
-
Auxiliary Treeの構築: \(O(K \log K)\)
Euler Tour TechniqueとSegment Treeを用いた場合
-
前計算: \(O(N)\)
-
Auxiliary Treeの構築: \(O(K (\log K + \log N))\)
実装 (ETT + Sparse Table)
#include<vector>
#include<algorithm>
using namespace std;
#define N 100000
#define NL 18
int fs[N], ls[N];
int depth[N];
int st[NL][3*N], lg[3*N];
int cur;
vector<int> g[N];
vector<int> g0[N];
void ett_dfs(int v, int p, int d) {
st[0][fs[v] = cur++] = v;
depth[v] = d;
for(int w : g[v]) {
if(w == p) continue;
ett_dfs(w, v, d+1);
st[0][cur++] = v;
}
ls[v] = cur-1;
}
void construct() {
cur = 0;
// Euler tour technique
ett_dfs(0, -1, 0);
lg[0] = lg[1] = 0;
for(int i=2; i<=cur; ++i) lg[i] = lg[i >> 1] + 1;
// Sparse Table
for(int i=0, b=1; i<lg[cur]; ++i, b<<=1) {
for(int j=0; j<(cur - (b<<1) + 1); ++j) {
st[i+1][j] = (depth[st[i][j]] <= depth[st[i][j+b]] ? st[i][j] : st[i][j+b]);
}
}
}
bool cmp_at(int x, int y) {
return fs[x] < fs[y];
}
inline int lca(int u, int v) {
int x = fs[u], y = fs[v];
if(x > y) swap(x, y);
int l = lg[y - x + 1];
return (depth[st[l][x]] <= depth[st[l][y - (1 << l) + 1]] ? st[l][x] : st[l][y - (1 << l) + 1]);
}
// 頂点vsを含むAuxiliary Treeを構築する
// 結果はg0に入る
// 返り値はAuxiliary Treeの根頂点
int stk[2*N];
inline int auxiliary_tree(vector<int> &vs, vector<int> g0[N]) {
sort(vs.begin(), vs.end(), cmp_at);
int k = vs.size();
for(int i=0; i<k-1; ++i) {
vs.push_back(lca(vs[i], vs[i+1]));
}
sort(vs.begin(), vs.end(), cmp_at);
int prv = -1;
int cur = 0;
for(int i=0; i<vs.size(); ++i) {
int v = vs[i];
if(prv == v) continue;
while(cur > 0 && ls[stk[cur-1]] < fs[v]) --cur;
if(cur > 0) {
g0[stk[cur-1]].push_back(v);
}
g0[v].clear();
stk[cur++] = v;
prv = v;
}
return stk[0];
}