概念
虚树是一棵树，相对于原树而言。它删去原树上某些点，再按原树父子关系连边构成的树。
它对树上算法有一定优化。假如一个树上问题仅与部分节点有关，如树形DP，DP值仅在部分节点有改变，那么就可以已这部分节点建成虚树，省略其他部分，复杂度为部分节点总和。
例：消耗战
本题的删边DP只与一点到顶点的最小边权边有关，但是要保证每个关键点的祖先都被计算。建虚树并DP是很好的选择。
建法
首先虚树保留关键点和所有他们的 lca，包括 lca 的 lca。发现两个关键点之间可能中途插入点。所以使用栈，反转扫描和建边的过程。
整个过程先将节点按dfn序排序，保证栈内存储节点在一条链上。若下一节点不在同一链上，则开始从栈顶删点直到栈次顶与当前节点在一条链上，注意弹出时要和次顶建边。此时栈顶向当前点与其的 lca 建边并弹出。现在的栈顶要么是刚才建边的 lca，就可以不管。否则就要压入建边的 lca 以保证两点 lca 有边。
int st[1000001];
vector<edge> f[1000001];
void btxs()
{
int top=0;
st[++top]=1;
for(int i=1;i<=k;i++)
{
int lca=getlca(st[top],din[i]);
while(dfn[st[top]]>=dfn[lca]&&top>1)
{
if(dfn[st[top-1]]<dfn[lca]) break;
f[st[top-1]].push_back((edge){st[top],0/*边权*/});
top--;
}
if(lca==st[top])
{
st[++top]=din[i];
}
else
{
f[lca].push_back((edge){st[top],0});
top--;
st[++top]=lca;
st[++top]=din[i];
}
}
while(top>1)
{
f[st[top-1]].push_back((edge){st[top],0});
top--;
}
}