在给定树上给出一些关键点，要求构造一棵树，满足所有关键点都在这棵树上，且树的形态与关键点在原树上的形态不变：即本不是祖先/后辈关系的点成为祖先/后辈是不允许的，本来是祖先/后辈的点如果在这棵树上也得是祖先/后辈。
更通俗一点的话，就是把所有关键点找出来，把两两关键点的 LCA 找出来，再根据之前的祖先后辈关系来连边，构成一棵新树。这棵新树就是原树的虚树。
一般可以在虚树上进行 DP，前提是这个 DP 只跟在虚树上的点和其它一些好维护的东西有关，比如两点距离（虚树把一条链的中间缩了，但这条链上的一些信息可以保留在虚树上对应的边上）。
先讲虚树构建方法，然后分析时间复杂度，再讲例题。
给出关键点集合，已知原树，求这个集合构成的虚树。
暴力一点，枚举任意两点及其 LCA，都放到集合里，再去重，再暴力构树。但是这样太暴力了。
朴素一点，把原树 dfs 一遍，一个点如果只有一个子树内有关键点，且自己不是关键点，就被缩，否则就不被缩。这样时间复杂度也不够优秀。
再回到第一个暴力做法，想一下去重后这个集合有多大。结合第二个做法，即最多有多少个节点自身不是关键点，且不只有一个子树内有关键点。
考虑到，每有一个上述说到的不只有一个子树内有关键点，且自身不是管简单的点，就说明至少有 2 个关键点在这个点为根的子树内。反过来——每两个关键点会诞生一个 LCA（或没有），然后这两个关键点没用了，而这个 LCA 会成为新的关键点。最多可以诞生关键点数量 -1 个新点。即——虚树大小跟关键点数量线性相关。
那么可以通过某种方法不重不漏地找出这些点，即可不与原树大小挂钩（虽然预处理需要）。
咕
标签：后辈,子树内,LCA,树上,虚树,关键点 From： https://www.cnblogs.com/0htoAi/p/16778808.html