虚树学习笔记

又是一个全机房只有我不会的知识点

同样，这篇文章也不适用于对这个知识点一无所知，且需要大量严谨证明的同学阅读

定义

虚树是一个用来优化树形dp的数据结构

考虑将原树中的某一个点集 $S$ 提取出来，构成一棵新的并能保持原树结构的一棵树。

为了保持结构，我们除了集合$S$的点之外，还需要在虚树中添加$S$中任意两点的。

因为有这么一条性质：

一个点集$S$中两两$lca$的集合，就是把$S$按dfn序排序后，相邻两点的$lca$的集合

这个性质很好理解

于是我们发现，总点数是$O(S)$级别的

构建

考虑求集合$S$的虚树

设关键点集合$T$表示$S$集合中两两点的$lca$，以及 $S$ 本身。用上面的那条性质就能轻松求出集合$T$

我们把集合$T$按照dfn序排序

接下来，我们使用一个栈维护一条从根下来的关键点链，然后不断对于这个栈进行操作，每次将新加进来的点与栈顶元素连一条边。

考虑从一条关键点链跳到另外一条关键点链上的过程，我们只需要不断弹栈，直到栈顶元素是当前新加进来点的祖先为止

感性理解就是有一条链从左往右不断移动，每个点只需要连上它在这条链的父亲

核心代码

sort(A + 1, A + K + 1, cmp_by_dfn);
for (int i = K; i > 1; --i) A[++K] = get_lca (A[i], A[i - 1]); A[++K] = 1;
sort(A + 1, A + K + 1, cmp_by_dfn);
K = unique (A + 1, A + K + 1) - A - 1;

for (int i = 1; i <= K; ++i)
{
	while (top && dfn[Stack[top]] + size[Stack[top]] - 1 < dfn[A[i]]) --top;
	if (top) add_edge (Stack[top], A[i]);
	Stack[++top] = A[i];
}

应用

虚树往往用来处理一些答案与关键点有关，且关键点总数$\sum k$不是很大的树形dp题

每次构建虚树，在虚树上进行dp即可，复杂度是$O((\sum k)* \log n)$的

具体来说，虚树上的一条边就相当于原树中的某一条链，但是这一条链上的dp转移与关键点无关

于是我们就可以预处理出原树中链上与关键点无关的转移（或者转移系数之类的），每次dp的时候只需要考虑当前虚树上的转移，虚树边上的转移直接利用预处理的信息即可

到了这里，我们就可以理解虚树的本质了

在与关键点有关的树形dp中，有一些边上的转移实际上是与关键点无关的，而如果我们对于每一次询问都$O(n)$进行dp的话，显然会有很多重复转移。于是我们可以预处理出这些重复的转移

这样便产生了虚树，它的本质就是把与当前关键点有关的转移单独提出来，单独进行转移，而虚树边上的转移都是与当前关键点无关，可以预处理出来的

因此虚树的思想还是对在暴力计算中冗余、重复处理的东西进行优化，从而优化时间复杂度