当我们遇到一类频繁询问关键点信息的题目时，往往数据范围颇大，而对关键点总和有一定限制，此时我们可以建立虚树，将问题规模转化为关键点总和级别的。
一、定义
什么是虚树？
当我们在树上有部分结点是无用的或用处不大的时，我们可以将其在树上删去，仅仅保留关键点和连接关键点的边。
如图，图中红点是关键点，右图即为建立的虚树。
二、性质
1. 空间线性性质
虚树的点数是O(n)的，因为其仅仅包含n个关键点和它们的lca，而lca的个数最多n−1个，故虚树结点数最多2n−1。
2. 结构相似性质
通过保留关键点的lca，我们可以尽可能地做到使虚树结构与原树相似，这样便使得我们的转化是有效的。
三、建立过程
1. 初始化
初始化ST表并将关键点按照Dfs序排序。
2. 得到虚树上的点
利用倍增求出排好序过后的关键点相邻两点的LCA，并加入关键点数组中，重新按照Dfs序排序并去重。
容易发现，此时虚树上的所有点都存在于数组中了。
3. 构建虚树
我们已经得到了虚树先序遍历的结果，现在我们要构建虚树，分为两种情况讨论。
（1）当前点在栈顶子树中
将栈顶和当前点连边，并将当前点入栈。
（2）当前点不在栈顶子树中
说明此时栈顶所在的一段链已经Dfs完毕，弹栈，重复执行该过程直到满足情况
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程