虚树是一种减少冗余、优化时间复杂度的树上问题优化。
在解决某些树上问题时，如果在多次询问中点数总体很大，但是解决问题的“关键点”数量很少，就可以利用虚树来将无用的点“剔除”，从而减少时间浪费。
构造虚树的方法
一般来说令关键点集合为 $V$，那么虚树包含着所有关键点和它们的 $\mathrm{LCA}$。虚树的边直接连接 $\mathrm{LCA}$ 和下面的点，而不再关心中间经过的点。
而构造虚树的一种常用做法就是利用单调栈维护虚树上的一条链。
记 $st_1$ 为栈顶元素，$st_2$ 为栈中第二个元素，以此类推。
- 首先我们发现虚树中的点只要祖先顺序不发生变化就可以任意地放点。所以为了方便我们先将根节点 $1$ 放入栈。
- 接下来，我们将 $V$ 中的元素按照 $\mathrm{dfn}$ 序排序。并依次插入单调栈。
- 第 $i$ 次插入中，我们记 $l=\operatorname{LCA}(p_i,st_1)$。
- 如果 $l=st_1$，说明 $p_i$ 接在 $st_1$ 下面，那么说明还没有更换链，直接将 $p_i$ 压入栈中。
- 如果 $l\neq st_1$，说明更换了链，那么就判断 $st_2$ 的 $\mathrm{dfn}$ 和 $l$ 的 $\mathrm{dfn}$ 的大小关系（不用担心只有一个元素，因为 $1$ 一直在栈中）。如果 $\mathrm{dfn}_l<\mathrm{dfn}_{st_2}$，就说明这个新链的起始点仍然在 $st_2$ 之上，那么可以直接弹出 $st_1$ 并建边。如果 $\mathrm{dfn}_l\ge\mathrm{dfn}_{st_2}$，就说明 $st_2$ 已经比新链高了。这时候如果 $\mathrm{dfn}_l=\mathrm{dfn}_{st_2}$，则说明 $st_2$ 恰好是新链的起始点，就可以直接压栈了；否则还需将 $st_1$ 弹出后将 $l$ 压入栈中。
- 最后在栈中还会剩下一条链，此时直接建边即可。
容易发现，这个过程的时间复杂度是 $O(n\log n)$ 的（$n$ 为关键点总数）。
例题：P2495 消耗战
首先想一下朴素 dp 怎么做。
不妨设 $dp_u$ 为使 $u$ 与子树中能源节点分离所需的最少代价，并设 $E$ 为能源节点集合。那么可得转移方程为
其中 $w(u,v)$ 为连接 $u,v$ 的边权。
这样子 dp 一次的时间复杂度是 $O(n)$ 的，总时间复杂度 $O(nq)$ 肯定过不了。
我们发现 $\sum|E|$ 比较小，所以考虑对每次询问，对 $E$ 中的节点建出虚树来，并在虚树上跑 dp。此时虚树的边权应为原树中两点路径上边权的最小值。
这样就过了，时间复杂度。。。$O(\sum|E|\log n)$。