关于虚树

瞎扯

某些树上问题，给了巨多节点，而实际上它们之中只有小部分能做出贡献，其余都是些水军，为杀尽 OIers的脑细胞 做出努力

考虑重新种一棵树，浓缩信息，简化节点个数，于是产生了 虚树。

大概是长这个样子：
红色结点是我们选择的关键点，即能够做出贡献的点。红色和黑色结点都是虚树中的点。黑色的边是虚树中的边。

因为任意两个关键点的 LCA 也是需要保存重要信息的，能够维持树的形态，所以我们需要保存它们的 LCA

显然，在保证爹不会变成儿子，儿子不会变成爹 爷爷也不行 的前提下，我们是可以随便把原有的点添到虚树中去的

你当然可以把原树所有的点都加到虚树中，只不过你这虚树建了跟建了一样

因此，为了方便，我们可以首先将 \(1\) 号节点加入虚树中，并且不会影响答案

构造

构造有两种方式，其中二次排序的方法常数较大，所以没写。才不会告诉你其实是因为我懒

本篇只介绍第二种，借助单调栈实现。

直接枚举所有关键点对，暴力求解 LCA 的时间复杂度显然不可接受。

我们可以将所有关键点先按 DFS 序排序，按顺序一个一个加到树里。刚开始树上只有 \(1\) 号点。

接下来，我们用一个栈维护在树上一条链上的所有点。这个栈内的所有点满足其 DFS 序单调递增。

每次要将下一个关键点(设为 \(u\))入栈前，求一下当前栈顶元素和这个关键点 \(u\) 的LCA \(p\)，分讨：

• 如果栈顶是 \(p\)，则可以知道我们加入的关键点 \(u\) 和栈中的点在一条链上，直接将关键点加入栈中即可。如图
  

• 如果此时栈顶不是 \(p\)（显然这时候 \(p\) 的 DFS 序比栈顶大，且 栈顶所在位置的子树业已处理完毕），说明 \(p\) 不在链上，将栈顶弹出，直到栈顶为 \(p\)，此时插入关键点。
  弹栈的时候记得把他和他父亲的边连一下。
  
  

酱紫我们的虚树就种好了捏~

Code

int LCA(int x,int y){//树剖LCA
	while(topf[x]!=topf[y]){
		if(dep[topf[x]]<dep[topf[y]]) swap(x,y);
		x=f[topf[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	return y;
}

bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}

int stk[N],top;
void build(){
	sort(a+1,a+1+k,cmp);
	stk[top=1]=1;
	for(int i=1;i<=k;i++){
		if(top==1){
			stk[++top]=a[i];
		}
		int lca=LCA(a[i],stk[top]);
		if(lca==stk[top]) continue;
		while(top>1 && dfn[stk[top-1]]>=dfs[lca]){
			addnew(stk[top-1],stk[top]);
			top--;
		}
		if(lca!=stk[top]){
			addnew(lca,stk[top]);
			stk[top]=lca;
		}
		stk[++top]=a[i];
	}
	while(top>0){//别忘了把栈里的连边
		addnew(stk[top-1],stk[top]);
		top--;
	}
	return;
}