虚树

虚树

OI Wiki 上有详细的图解,这里就不赘述做法了。

简单说一下思想。

虚树就是将询问中涉及到的点从原树中拿出来,重新建树。这样就保证虚树中只涉及询问的点以及这些点的 $LCA$。从而起到控制复杂度的作用。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 以1为根节点,只有单向边
int stk[maxn], top;
vector<int> g[maxn];
void clean(int u) {
for (auto &v : g[u]) clean(v);
g[u].clear();
}
inline void addEdge(int u, int v) { g[u].push_back(v); }
void build(vector<int> &ps) {
clean(1);
sort(ps.begin(), ps.end(),
[&](const int &a, const int &b) { return dfn[a] < dfn[b]; });
stk[top = 1] = 1;
for (auto &u : ps) {
if (u == 1) continue;
int fa = lca(u, stk[top]);
if (fa != stk[top]) {
while (dfn[fa] < dfn[stk[top - 1]]) {
addEdge(stk[top - 1], stk[top]);
--top;
}
addEdge(fa, stk[top--]);
if (dfn[fa] > dfn[stk[top]]) stk[++top] = fa;
}
stk[++top] = u;
}
for (int i = 1; i < top; i++) addEdge(stk[i], stk[i + 1]);
}

例题 luogu2495