虚树，是一种针对树上点集的强力运算。它可以在\(O(k\log k)\)（其中\(k\)是点集大小）的时间内，建出一棵包含点集中所有节点，以及其中某些点的lca的树出来。这棵树就被称作虚树。之后就可以在虚树上进行操作了，例如树形DP等。
建出虚树的操作主要是这样的：
-
我们维护一个栈，从栈顶到栈底构成原树上一条深度递减的链。注意这条链不是完整的链——它只记录了链上的关键节点。
-
我们首先将原树的根节点加入虚树，方便维护。接着，将点集中所有点按照dfs序排序，然后依次加入虚树。
-
当一个点被加入虚树时，如果栈为空，直接将该点加入栈，并直接结束函数；否则，求出它与栈顶节点的LCA。
-
如果栈中第二个元素的深度小于LCA的深度，在虚树上连一条边\((\text{栈中第二个元素},\text{栈顶元素})\)，并弹出栈顶节点。重复此操作，直到第二个元素的深度大于等于LCA的深度。
-
如果栈顶元素的深度小于LCA的深度，连一条边\((LCA,\text{栈顶元素})\)，并弹出栈顶元素。
-
如果栈顶元素不同于LCA，将LCA入栈。
-
将（3）中那个点入栈，并结束该函数。
-
在所有东西全部加入虚树后，清空栈，在清空的过程中同时连边。
代码：
void ins(int x){
if(!tp){stk[++tp]=x;return;}
int lca=LCA(x,stk[tp]);
while(tp>=2&&dep[lca]<dep[stk[tp-1]])v[stk[tp-1]].push_back(stk[tp]),tp--;
if(tp&&dep[lca]<dep[stk[tp]])v[lca].push_back(stk[tp--]);
if(!tp||stk[tp]!=lca)stk[++tp]=lca;
stk[++tp]=x;
}
理解：
因为我们事先将节点按照dfs序排序，所以当新节点的深度大于栈顶节点深度的时候，就意味着原树中栈顶节点子树内所有节点都已经被加入虚树，可以弹出了。
然后，这个lca为了维护虚树的形态，也应该被加入虚树。
总复杂度\(O(k\log k)\)，瓶颈在于按照dfs序排序。
一些定义：
虚树：即上文代码所建出的树
原树/实树：原本的树
实点：给出点集中的点
虚点：在建出虚树时为了维护形态而添加的点（即实点的LCA之类）
树外点：原树中不在虚树内的点
树点：虚树内的点（大部分没有歧义的时候，“节点”就特指树点）