虚树一般用于树形DP中，此类问题通常询问次数很多但每次询问涉及到的点数很少。若每次询问均对整棵树进行DP，时间复杂度是巨大的。所以我们采用虚树这种数据结构。
虚树的构建
- 虚树由询问点和询问点的LCA构成。
- 我们可以先处理出原树的dfs序，从dfs序由小到大来遍历询问点，并通过栈来维护一条dfs序最大的链，在元素出栈时建边。根节点首先要加入栈。
-
如果栈中只有一个元素，将该点 \(u\) 加入栈；
否则，求出 \(\operatorname{LCA}(stk[top],u)\)，进行下一步操作。 -
若 \(stk[top]=LCA\)，将 \(u\) 加入栈即可。
-
若 \(dep[stk[top-1]]>dep[LCA]\)，\(stk[top]\) 与\(stk[top-1]\) 的子树都已构建完毕，将 \(stk[top-1]\) 与 \(stk[top]\) 之间连一条边，将 \(stk[top]\) 弹出栈。循环此步骤至 \(dep[stk[top-1]]\le dep[LCA]\)。
此处能保证正确性，是因为栈中维护的是一条链，也就是 \(LCA\) 是 \(stk[top-1]\) 的祖先，\(stk[top-1]\) 是 \(stk[top]\) 的祖先，且 \(dep[stk[top-1]]>dep[LCA]\)。 -
若 \(dep[stk[top-1]]<dep[LCA]\)，\(stk[top]\) 的子树已经构建完毕，将 \(LCA\) 与 \(stk[top]\) 连一条边，将 \(stk[top]\) 弹出栈，将 \(LCA\) 与 \(u\) 加入栈。
-
若 \(dep[stk[top-1]]=dep[LCA]\)，\(LCA\) 就是 \(stk[top-1]\)，将 \(LCA\) 与 \(stk[top]\) 连一条边，将 \(stk[top]\) 弹出栈，将 \(u\) 加入栈。
-
- 具体代码如下（采用了一些简化写法）
inline void insert(int u){
if(top==1){stk[++top]=u;return;}
int lca=LCA(u,stk[top]);
if(lca==stk[top]){stk[++top]=u;return;}
while(top>1&&dep[lca]<=dep[stk[top-1]]){
add(stk[top-1],stk[top]);
--top;
}
if(lca!=stk[top])add(lca,stk[top]),stk[top]=lca;
stk[++top]=u;
}