虚树

在树上 DP 时，有时会有大量的无用节点，遍历求解效率低，可以通过建立 虚树——一种只包含有用节点的树，来优化求解过程。

虚树的建立

朴素算法

1. 将关键点按 DFS 序排序；
2. 遍历一遍，任意两个相邻的关键点求一下 LCA，并且哈希表判重；
3. 然后根据原树中的祖先后代关系建树。

单调栈做法

先将树根 root 加入单调栈。然后，对于每一个关键节点（已排序），计算它与栈顶的 LCA，分类讨论：

1. 如果 LCA 就是栈顶（即这个关键节点与栈顶在一条链上），则删除这个关键节点的所有边，将它压入栈，退出。
2. 将栈顶和次栈顶连边，将栈顶弹出，如此重复多次，直到次栈顶为这个关键节点的祖先。
3. 若 LCA 为当前栈顶的祖先，将 LCA 与当前栈顶连边并弹出栈顶。
4. 否则删除 LCA 的所有边，在 LCA 与栈顶加边，在将栈顶改为 LCA。
5. 删除这个关键节点的所有边，将它压入栈。

遍历完每一个关键节点后，别忘了处理栈中的点，将它们相邻两点加边。

//origin 表示原树，virt 表示虚树
virt::total=0;
k=read();
for(i=1;i<=k;i++)query[h[i]=read()]=true;
std::sort(h+1,h+k+1,cmp);
stack[top=1]=h[1];
for(i=2;i<=k;i++){
	int _lca=origin::lca(h[i],stack[top]);
	if(_lca!=stack[top]){
		while(origin::dfn[_lca]<origin::dfn[stack[top-1]])virt::add(stack[top-1],stack[top]),top--;
		if(origin::dfn[_lca]>origin::dfn[stack[top-1]])virt::head[_lca]=0,virt::add(_lca,stack[top]),stack[top]=_lca;
		else virt::add(_lca,stack[top--]);
	}
	virt::head[h[i]]=0,stack[++top]=h[i];
}
for(i=1;i<top;i++)virt::add(stack[i],stack[i+1]);

例题