题解 P6135 【【模板】虚树】

> 对于一类特殊的树上问题，虚树通常可以简化树的结构，从而降低时间复杂度。 ## 概念 有这样一类树上数据结构题，每组询问会涉及树中若干个**关键点**，但所有询问涉及的关键点总数并不多（通常需要输入这些关键点，所以也不可能太多，一般与树的大小同阶）。 对于这样的问题，每次询问我们并不需要知道整棵树的结构信息，而只需要知道关键点之间的结构信息。那么，我们可以考虑建出一棵**虚树**，只保留关键点间的相对结构。 为了保留相对结构，我们除了要将关键点保留，还需要将它们两两的 LCA 保留，同时虚树中一条边的边权为原树中对应路径的边权和。 可以证明，树上 $k$ 个关键点两两的 LCA 个数不超过 $k-1$，这意味着虚树的节点数是 $\mathcal O(k)$ 的，非常优秀。 ## 构造 与[笛卡尔树](https://www.xht37.com/笛卡尔树-学习笔记/)的构造类似，核心都是用栈维护右链。 考虑按 dfs 序依次将关键点插入虚树，为了方便，我们新增一个超级根指向原来的树根。 一开始栈中只有一个超级根，当要加入点 $u$ 的时候，我们求出 $u$ 与栈顶元素 $v$ 的 LCA（由于超级根的存在，栈不会为空），记为点 $p$。 若 $p = v$，说明 $v$ 是 $u$ 的祖先，因此直接将 $u$ 加入栈，延长右链。 否则说明 $u$ 和 $v$ 在 $p$ 的不同子树中，因此我们要更新右链，注意此时 $p$ 一定在右链中，但不一定在栈中。 所以我们不断退栈并连边，直到栈顶的第二个元素的深度比 $p$ 小，分类讨论一下栈顶和 $p$ 是否为同一个点，然后退栈，加入 $p,u$。 最后将栈中的点连边即可，时间复杂度 $\mathcal O(n \log n) - \mathcal O(k \log k)$。 #### 【模板】[P6135 【模板】虚树](https://www.luogu.com.cn/problem/P6135) ```cpp const int N = 2e5 + 7; int n, k, rt, f[N][21], g[N], d[N], dfn[N], tot, s[N], t; vi e[N], p; void dfs(int x) { dfn[x] = ++tot; for (auto y : e[x]) { d[y] = d[x] + 1; for (int i = 1; f[y][i-1]; i++) f[y][i] = f[f[y][i-1]][i-1]; dfs(y); } } inline int lca(int x, int y) { if (d[x] > d[y]) swap(x, y); for (int i = 20; ~i; i--) if (d[f[y][i]] >= d[x]) y = f[y][i]; if (x == y) return x; for (int i = 20; ~i; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } inline void virtual_tree(vi p) { sort(p.begin(), p.end(), [](int x, int y) { return dfn[x] < dfn[y]; }); for (int u : p) { int lca = ::lca(u, s[t]); if (lca != s[t]) { while (t && d[s[t-1]] >= d[lca]) g[s[t]] = s[t-1], --t; if (s[t] != lca) g[s[t]] = lca, s[t] = lca; } s[++t] = u; } while (t--) g[s[t+1]] = s[t]; } int main() { rd(n), rd(k); for (int i = 1; i <= n; i++) rd(f[i][0]), e[f[i][0]].pb(i), g[i] = -1; rt = e[0][0], d[rt] = 1, dfs(rt); for (int i = 1, x; i <= k; i++) rd(x), p.pb(x); virtual_tree(p); for (int i = 1; i <= n; i++) if (!~g[i]) prints("-1 -1"); else if (!g[i]) prints("0 0"); else print(g[i], ' '), print(d[i] - d[g[i]]); return 0; } ```