什么是虚树？

当我们遇到一类频繁询问关键点信息的题目时，往往数据范围颇大，而对关键点总和有一定限制，此时我们可以建立虚树，将问题规模转化为关键点总和级别的。

一、定义

什么是虚树？

当我们在树上有部分结点是无用的或用处不大的时，我们可以将其在树上删去，仅仅保留关键点和连接关键点的边。

如图，图中红点是关键点，右图即为建立的虚树。

二、性质

1. 空间线性性质

虚树的点数是O(n)的，因为其仅仅包含n个关键点和它们的lca，而lca的个数最多n−1个，故虚树结点数最多2n−1。

2. 结构相似性质

通过保留关键点的lca，我们可以尽可能地做到使虚树结构与原树相似，这样便使得我们的转化是有效的。

三、建立过程

1. 初始化

初始化ST表并将关键点按照Dfs序排序。

2. 得到虚树上的点

利用倍增求出排好序过后的关键点相邻两点的LCA，并加入关键点数组中，重新按照Dfs序排序并去重。

容易发现，此时虚树上的所有点都存在于数组中了。

3. 构建虚树

我们已经得到了虚树先序遍历的结果，现在我们要构建虚树，分为两种情况讨论。

（1）当前点在栈顶子树中

将栈顶和当前点连边，并将当前点入栈。

（2）当前点不在栈顶子树中

说明此时栈顶所在的一段链已经Dfs完毕，弹栈，重复执行该过程直到满足情况