虚树是用来解决树上的一些特定点问题的好方法。建立虚树的本质是缩二度点。具体来讲是这样的：
维护一个栈，表示虚树的最右链。栈从顶到底深度递减。一开始先 push 进根，方便操作。下面定义 stk[x] 为从栈顶向下数的第 x 个元素。
当加入一个点的时候，执行下述操作：
-
若栈只有根元素，那直接 push 进栈，return. 否则求出当前点和栈顶的 LCA.
-
若
stk[2]的深度比LCA大，则 \(pop\) 掉stk[1]并连边stk[2]，重复该过程使得stk[2]的深度小于等于LCA. -
现在
stk[1]和 LCA 的关系是不确定的。假如stk[1]比LCA深，那需要 addedge 之后 pop 掉。 -
假如
stk[1]不是 LCA，需要将 LCA 入栈。 -
原来需要加入的点入栈。