虚树学习笔记【转载】

概述

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

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

介绍

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

我们看一个虚树的例子(黑色点为关键点,红色点为 LCA):
《虚树学习笔记【转载】》
可以看到,所有关键点都留了下来,而且树的形态也被完好的保存了下来。往往未被选中的点并不影响答案,这些未被选中的点,以路径长度的形式存在于虚树中。

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

我们考虑这样一个事实:假设 和 的 LCA 是 ,而如果 与 的 LCA 是 且 ,那么 与 的 LCA 也是 。考虑反证法,如果 与 的 LCA 不是 的话,那么 必然在 的子树中,由于 ,所以 到根的距离必然小于 到根的距离,这与「 在 的子树中」这一事实矛盾。

基于这一个事实,我们可以发现,所有 LCA 是 的一堆点,都可以被看作一个点(每个点对之后的 的贡献都是一样的)。所以对于 来说,可考虑的点就至多只有 个了。同理,所有 LCA 是 的一堆点,又可以被看作一个点。所以对于 来说,可考虑的点就至多只有 个了。一直压缩下去,对于 来说,可以考虑的点就至多只有 个了。至于 至多只有一个点可考虑,无法形成新的 LCA。所以 不可能存在。

我们这就证明了定理一,定理一是虚树复杂度的保障。事实上, 的上限在下图这一情况下达到(黑色是被选择的点,红色是 LCA):
《虚树学习笔记【转载】》

构造

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

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

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

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

如图所示, 点必然在右链上,但不一定是栈中存在的点。
《虚树学习笔记【转载】》
为了维护右链,我们必须一直退栈,退到栈顶的第二个元素的深度比 小(因为 可能不存在于栈中,我们要加入这个点),并且退栈的过程中连边。整个过程如下图所示:
《虚树学习笔记【转载】》
一直重复这个过程,直到所有关键点都被加入。将最后还在栈中的点连上边即可。

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

代码

m = getint();
for (int i = 0; i < m; ++i) {a[i] = getint(); vis[a[i]] = true;}
sort(a, a + m, cmpdfn);
for (int i = 0; i < m; ++i) {
    x = lca(a[i], sta[tail]);
    while (tail > 0 && dep[sta[tail-1]] >= dep[x]) {
        y = sta[tail--];
        VTree::ins(sta[tail], y);
    }
    if (sta[tail] != x) {
        VTree::ins(x, sta[tail--]);
        sta[++tail] = x;
    }
    sta[++tail] = a[i];
}
while (tail) {
    y = sta[tail--];
    VTree::ins(sta[tail], y);
}

/* balabala ... */

for (int i = 0; i < m; ++i) vis[a[i]] = false;
VTree::clear();

题目

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

BZOJ 2286
BZOJ 3572
BZOJ 3991

来源

Sengxian’s Blog

  1. MagHSK说道:

    这时候就要艾特一下作者@Sengxian:disqus

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据