虚树

参考资料

• 虚树 - OI Wiki

简介

虚树（Virtual Tree）用于一类只关心若干 关键点 的树上问题。它只保留关键点及它们两两的 LCA，并按原树的祖先关系连边，得到一棵规模为 $O(k)$ 的树（$k$ 为关键点数），从而把每次询问的复杂度降到只与关键点数相关。构建时先把关键点按 DFS 序排序，再用下面两种方法之一连边。

二次排序

把关键点与相邻两点的 LCA 一并加入，按 DFS 序排序去重，再让每对相邻点的 LCA 作父亲连边。

270 Bcpp

int build(int k)
{
	auto cmp=[](int u,int v){return dfn[u]<dfn[v];};
	sort(a+1,a+k+1,cmp);
	for(int i=1;i<k;i++)a[k+i]=lca(a[i],a[i+1]);
	a[k<<=1]=1;
	sort(a+1,a+k+1,cmp);
	k=unique(a+1,a+k+1)-a-1;
	for(int i=1;i<k;i++)H[lca(a[i],a[i+1])].push_back(a[i+1]);
	return k;
}

单调栈

按 DFS 序遍历关键点，用单调栈维护当前点到根的一条链：遇到新点时弹出深度大于其与栈顶 LCA 的部分并连边，再把 LCA 与新点入栈。

344 Bcpp

void build(int k)
{
	auto cmp=[](int u,int v){return dfn[u]<dfn[v];};
	sort(a+1,a+k+1,cmp);
	int t=0;s[++t]=1;
	for(int i=1;i<=k;i++)
	{
		if(a[i]==1)continue;
		int l=lca(a[i],s[t]);
		while(dep[s[t-1]]>=dep[l])H[s[t-1]].push_back(s[t--]);
		if(s[t]!=l){H[l].push_back(s[t]);s[t]=l;}
		s[++t]=a[i];
	}
	while(t>1)H[s[t-1]].push_back(s[t--]);
}

例题

洛谷 P2495 【模板】虚树 / [SDOI2011] 消耗战

给定 $n$ 个点的带边权树，根为 $1$。$m$ 次询问，每次给出 $k$ 个关键点，求删去若干条边、使所有关键点都与根不连通的最小总代价。