Skip to main content

虚树

参考资料​

二次排序​

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;
}

单调栈​

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] 消耗战

在一场战争中，战场由 nn 个岛屿和 n−1n-1 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 11 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 kk 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。

侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 11 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 mm 次，所以我们只需要把每次任务完成即可。