虚树

之前学过至少两遍了,但是总是忘…重新学一下,写一篇博客备忘。

简介

有这么一类题目:

给出一颗树,有一些询问,每次询问给出一些关键点,询问次数很多,但是总询问点数和树的大小同阶。

但是,如果暴力计算,每次的复杂度是树的大小,复杂度不对。那么如果能通过一种方法使得每次询问的复杂度和询问点数有关而不是树的大小有关,那么就能通过此题。

这个时候,可以通过虚树(virtual tree)来解决这一类问题。

算法概述

如果每次的答案只和询问点和询问点和询问点之间的$LCA$有关,那么可以把询问点和$LCA$抽离出来,新建一颗树,那么这棵树就是虚树,这样做的话虚树既不会改变原树的结构,也不会改变原树的性质。这样建出的树的大小和询问点同阶。

定理: n个点两两之间的LCA不会超过n-1个

证明

如果$x$和$y$的LCA是$a$,$y$和$z$的LCA是$b$,因为$LCA$的定义是dfs序中深度最小的一个点,那么$x$和$z$的LCA一定是$a$和$b$的中的一个,所以对于$n$个点中的第一个点,和剩下的$n-1$个点最多形成$n-1$个LCA,剩下的点之间不会产生新的LCA,所以最多是$n-1$个。

这样我们证明了虚树的复杂度,问题在于构造虚树。

这里的做法是用栈维护最右边的链

这个最右边指的不是图中的左右,我们把最右指dfs序最小的点

算法过程如下,简单来说是个模拟:

  1. 先把询问点按dfs序排序。
  2. 顺次遍历询问点
  3. 如果栈为空,压点入栈,返回操作2
  4. 取出栈顶元素,求出当前点和栈顶的LCA
  5. 如果LCA就是栈顶元素,则说明这个点在当前栈维护的那条链里面,压入栈,返回操作2
  6. 如果LCA不是栈顶,那么说明当前点在一条新链里面,那么需要弹掉在原本栈中的深度大于LCA的点。弹掉栈顶,如果新栈顶满足深度大于LCA,就把之前的栈顶和新栈顶连边,重复这一过程直到栈顶不满足条件。
  7. 如果栈顶不是LCA,那么把LCA压入栈顶;最后一个满足条件的栈顶元素和LCA连边。返回操作2。
  8. 所有点的操作执行完以后,如果当前的栈非空,相当于还剩下一条链。那么不停弹栈,把栈中相邻的元素连边。

这样我们就维护了最右边的链,建好了虚树。

代码

传入询问点集,返回虚树的点集

例题

1.BZOJ2285 消耗战

题意

虚树最经典的模板题。多次询问,每次可以删掉一些边,询问使得给出$k$个点不和1号点联通的最小代价。

题解

暴力DP一次是$O(n)$的。我们可以建立出虚树,然后DP,新建立的虚树两点之间的边权为它们之间的最短边,倍增维护即可。复杂度$O(\sum k_i \log k_i)$

代码

2.BZOJ3572 世界树

题意

给出一颗树,多次询问,每次给出一些关键点,对于每个非关键点定义控制它的点为距离它最近的(如果相同距离就是编号小的)。求出每个关键点控制点的个数。

题解

比较明显的虚树题,但是问题在于建立出虚树以后怎么计算。

先可以通过两遍dfs预处理虚树上的点被哪个点控制。

然后问题可以简化,考虑虚树上的一条边和边上的非虚树点的非虚子树。如果两头都是关键点,可以倍增找到最边界,统计入答案。如果不是,则需要另外考虑。

其实可以直接分“控制点是否相同”两种情况考虑

  1. 如果控制边上两头的点的相同。那么这条边的答案属于那个控制点。
  2. 如果不同,则也是倍增,计算当前倍增到的点和两头的点被控制点的距离进行比较,单调性依然存在。

这样做会有一些问题。和虚树上的边没有关系的点不会被计算到。

解决方法是把一个点的答案看做他子树的所有点,然后减去不合法的贡献。

细节问题很多,调了好久。

写出的最大的问题是,统计最近点的时候应该先从下往上传,然后从上往下传。不应该是从上往下然后往上。

因为这样的话,会漏掉这么一种情况。

2的最近点应该是1,但是会算错。(反正这也是个很sb的问题)

不知道为什么不删调试语句BZOJ上有6KB(人傻代码丑

3.BZOJ3879 SvT

题意

给出一个串,多次询问,给定一些后缀,求这些后缀的两两$LCP$之和

题解

没那么明显的虚树。如果考虚树,一般都比较明显。

感觉这个题比上一个好打而且好想。

直接建出后缀树以后把每次询问的关键点建立虚树,最后从下网上统计答案。

感觉我后缀树学的不太好,复习了一下。

暴力的方法,把每个后缀插入Tire,每个点被插入加一,最后把权值为1的点缩起来,得到后缀树。

这样得到了后缀树(SuffixTree),构建后缀树的方法是对反串建SAM然后parent树就是后缀树。

树上的每一个节点的深度(送根节点开始到这个点的串的长度)为SAM中的$maxlen$。

而第$i$个后缀所对应的后缀树节点就是SAM中第$len-i$个插入的点的编号,两个点的LCA所对应的就是这两后缀的LCP。

题目就是要求两两关键点LCA的深度和。方法同 BZOJ3238差异,分层计算,对于每个点的贡献就是$C(size[cur],2) \times (mxl[cur]-mxl[par[cur]])$,这里就不详细解释。

事实上我之前想的计算答案的方法是把每个点的子树总合法点对个数算出来然后减去对应每一颗子树中合法点对个数,感觉是也可以的。

关于取膜,它死了(模数大于最大答案海星。关于long long,也不需要。

还是常数巨大,不过还是过了。不开O2常数超级加倍(x5)也是很刺激。

Leave a Reply

Your email address will not be published. Required fields are marked *