虚树
虚树
考虑这样一类问题：
给定一颗大小为$n$的树。之后要求回答$q$个请求，第$i$个请求给定$k_i$个特殊点，要求在树上进行DP计算，且只有特殊点会对我们的dp产生影响，其余非特殊点的逻辑非常简单。比如说我们的DP是要找到这些特殊点中的最大独立集大小。且$1\leq n,q,\sum_{i=1}^qk_i\leq 10^5$。
我们当然可以暴力回答每个请求，时间复杂度为$O(nq)$，但是这样太慢了。我们可以将多个非特殊点进行压缩来提速。
具体的方法非常简单。首先我们将特殊点全部按照dfn序（即dfs时到达每个顶点的时间戳）排序，我们记得到的顶点序列为$v_1,v_2,\ldots,v_k$。之后对于$1\leq i\lt k$，我们将$v_i$和$v_{i+1}$的lca加入到序列中。然后我们再重新对序列按照顶点的dfn序进行排序并去重。假设这时候得到的序列为$u_1,\ldots,u_t$。之后我们通过维护一个栈，初始为空，遍历$1$到$t$，记当前考虑的数为$i$：
- 将栈尾部所有不是$u_i$祖先的顶点弹出。
- 将栈尾元素设置为$u_i$的父亲。
- 将$u_i$入栈
上面的流程会给我们提供一颗虚树。我们可以在虚树上dp，来加快计算的速度。
这颗虚树有下面性质：
- 所有叶子都是特殊顶点。
- 树的大小为$O(2n-1)$。
- 祖先后代关系与原树相同。
下面给出算法的一些正确性的证明：
任意两个特殊顶点的lca都存在于虚树中
证明：
当顶点只有一个时，显然一定成立。假设当顶点数小于$k$时，命题一定成立。
对于长度为$k$的按照dfn序排序的序列$v_1,\ldots,v_k$。可以发现$lca(v_1,v_k)=lca(lca(v_1,v_2),lca(v_2,v_3),\ldots,lca(v_{k-1},v_k))$。现在记$l_i=lca(v_i,v_{i+1})$。我们只需要证明$lca(l_1,\ldots,l_{k-1})\in \left\{l_1,\ldots,l_{k-1} \right\}$。由于$l_i,l_{i+1}$同时都是$v_{i+1}$的祖先，因此$lca(l_i,l_{i+1})\in \left\{l_i,l_{i+1}\right\}$。根据假设有$lca(l_1,\ldots,l_{k-1})\in \left\{l_1,\ldots,l_{k-1} \right\}$，因此命题成立。