虚树

Published: by Creative Commons Licence

  • Tags:

虚树

考虑这样一类问题：

给定一颗大小为n的树。之后要求回答q个请求，第i个请求给定ki个特殊点，要求在树上进行DP计算，且只有特殊点会对我们的dp产生影响，其余非特殊点的逻辑非常简单。比如说我们的DP是要找到这些特殊点中的最大独立集大小。且1≤n,q,∑qi=1ki≤105。

我们当然可以暴力回答每个请求，时间复杂度为O(nq)，但是这样太慢了。我们可以将多个非特殊点进行压缩来提速。

具体的方法非常简单。首先我们将特殊点全部按照dfn序（即dfs时到达每个顶点的时间戳）排序，我们记得到的顶点序列为v1,v2,…,vk。之后对于1≤i<k，我们将vi和vi+1的lca加入到序列中。然后我们再重新对序列按照顶点的dfn序进行排序并去重。假设这时候得到的序列为u1,…,ut。之后我们通过维护一个栈，初始为空，遍历1到t，记当前考虑的数为i：

  1. 将栈尾部所有不是ui祖先的顶点弹出。
  2. 将栈尾元素设置为ui的父亲。
  3. 将ui入栈

上面的流程会给我们提供一颗虚树。我们可以在虚树上dp，来加快计算的速度。

这颗虚树有下面性质：

  • 所有叶子都是特殊顶点。
  • 树的大小为O(2n−1)。
  • 祖先后代关系与原树相同。

下面给出算法的一些正确性的证明：

任意两个特殊顶点的lca都存在于虚树中

证明：

当顶点只有一个时，显然一定成立。假设当顶点数小于k时，命题一定成立。

对于长度为k的按照dfn序排序的序列v1,…,vk。可以发现lca(v1,vk)=lca(lca(v1,v2),lca(v2,v3),…,lca(vk−1,vk))。现在记li=lca(vi,vi+1)。我们只需要证明lca(l1,…,lk−1)∈{l1,…,lk−1}。由于li,li+1同时都是vi+1的祖先，因此lca(li,li+1)∈{li,li+1}。根据假设有lca(l1,…,lk−1)∈{l1,…,lk−1}，因此命题成立。