Sengxian's Blog

概述

在 OI 比赛中，有这样一类题目：给定一棵树，另有多次询问，每个询问给定一些关键点，需要求这些关键点之间的某些信息。询问数可能很多，但满足所有询问中关键点数量的总和与树的大小同阶。

由于询问数可以非常多，每次无法遍历整棵树，这类题目看似没有办法做，但实际上，我们可以用一种叫做虚树（virtual tree）的技术来解决这一问题。

介绍

简单来说，虚树是对一颗有根树中的一些关键点而言的，虚树将树的大小压缩到与关键点的数量同阶。虚树中包含了所有的关键点，也包含了所有关键点两两之间的 LCA（lowest common ancestor, 最近公共祖先）（LCA 的数量不超过关键点的个数，稍后有证明），这就保证了虚树不会丧失原有的树形结构，同时尽可能地压缩了树的大小。同时虚树中 $u$ 到 $v$ 的边权定义为原树中 $u$ 到 $v$ 的最短路径。

我们看一个虚树的例子（黑色点为关键点，红色点为 LCA）：

可以看到，所有关键点都留了下来，而且树的形态也被完好的保存了下来。往往未被选中的点并不影响答案，这些未被选中的点，以路径长度的形式存在于虚树中。

定理一：在一棵有根树中，任选 $k$ 不重复的点，这 $k$ 个点两两之间的不同的 LCA 个数不超过 $k - 1$ 个。
证明：我们考虑求出 $k$ 个点两两之间的 LCA，将其按照到根的距离从到大到小排序，记为 $l_1, l_2, \cdots, l_m$。

我们考虑这样一个事实：假设 $u$ 和 $v$ 的 LCA 是 $l_1$，而如果 $u$ 与 $w$ 的 LCA 是 $l_x$ 且 $l_x \neq l_1$，那么 $v$ 与 $w$ 的 LCA 也是 $l_x$。考虑反证法，如果 $v$ 与 $w$ 的 LCA 不是 $l_x$ 的话，那么 $l_x$ 必然在 $l_1$ 的子树中，由于 $x > 1$，所以 $l_x$ 到根的距离必然小于 $l_1$ 到根的距离，这与「$l_x$ 在 $l_1$ 的子树中」这一事实矛盾。

基于这一个事实，我们可以发现，所有 LCA 是 $l_1$ 的一堆点，都可以被看作一个点（每个点对之后的 $l$ 的贡献都是一样的）。所以对于 $l_2$ 来说，可考虑的点就至多只有 $k - 1$ 个了。同理，所有 LCA 是 $l_2$ 的一堆点，又可以被看作一个点。所以对于 $l_3$ 来说，可考虑的点就至多只有 $k - 2$ 个了。一直压缩下去，对于 $l_{k - 1}$ 来说，可以考虑的点就至多只有 $2$ 个了。至于 $l_k$ 至多只有一个点可考虑，无法形成新的 LCA。所以 $l_k$ 不可能存在。

我们这就证明了定理一，定理一是虚树复杂度的保障。事实上，$k - 1$ 的上限在下图这一情况下达到（黑色是被选择的点，红色是 LCA）：

构造

虚树的构造与笛卡尔树的构造类似，核心思想都是维护最右边的链。

我们先将关键点按照 DFS 序排序，然后考虑顺序将关键点插入。为了方便，我们新增一个超级根指向原来的树根。

我们用一个栈来维护虚树的右链，一开始，栈中只有一个超级根。当要加入点 $u$ 的时候，我们求出 $u$ 与栈顶元素 $v$ 的 LCA（由于我们维护虚树的右链，所以超级根始终在栈中，栈不会为空），记为点 $p$，现在有两种情况：

1. $p = v$，说明 $u$ 到 $v$ 是一条直链，此时直接将 $u$ 加入栈即可，右链被延长了。
2. $p \neq v$，那就说明 $u$ 和 $v$ 在 $p$ 的不同子树中，这时候要对右链进行更新。

如图所示，$p$ 点必然在右链上，但不一定是栈中存在的点。

为了维护右链，我们必须一直退栈，退到栈顶的第二个元素的深度比 $p$ 小（因为 $p$ 可能不存在于栈中，我们要加入这个点），并且退栈的过程中连边。整个过程如下图所示：

一直重复这个过程，直到所有关键点都被加入。将最后还在栈中的点连上边即可。

结合之前的证明，容易看出，所有的点的 LCA 都在虚树中。

代码

inline bool cmp(const int &i, const int &j) {
    return dfn[i] < dfn[j];
}

void build(int vectrices[], int k) {
    static int stk[MAX_N];
    sort(vectrices, vectrices + k, cmp);

    stk[sz++] = 0;
    for (int i = 0; i < k; ++i) {
        int u = vectrices[i], lca = ::lca(u, stk[sz - 1]);
        if (lca == stk[sz - 1]) stk[sz++] = u;
        else {
            while (sz - 2 >= 0 && dep[stk[sz - 2]] >= dep[lca]) {
                addEdge(stk[sz - 2], stk[sz - 1]);
                sz--;
            }

            if (stk[sz - 1] != lca) {
                addEdge(lca, stk[--sz]);
                stk[sz++] = lca, vectrices[cnt++] = lca;
            }

            stk[sz++] = u;
        }
    }
    for (int i = 0; i < sz - 1; ++i) addEdge(stk[i], stk[i + 1]);

题目

建出虚树以后，剩下的部分基本上就与虚树这个知识点没什么关系了，往往需要虚树上进行树形 DP，这里给几道题，就不详细解释了。

BZOJ 2286
BZOJ 3572
BZOJ 3991