跳到主要内容

虚树

参考资料​

二次排序​

void build()
{
	sort(h+1,h+k+1,cmp);
	for(int i=1;i<k;i++)h[k+i]=lca(h[i],h[i+1]);
	h[k<<=1]=1;
	sort(h+1,h+k+1,cmp);
	k=unique(h+1,h+k+1)-h-1;
	for(int i=1;i<k;i++)
	{
		int u=lca(h[i],h[i+1]),v=h[i+1];
		H[u].push_back({v,dis[v]});
	}
}

单调栈​

void build()
{
	s[1]=1;
	int t=1;
	for(int i=1;i<=k;i++)
	{
		if(h[i]==1)continue;
		int l=lca(h[i],s[t]);
		while(t>1&&dep[s[t-1]]>=dep[l])
		{
			int u=s[t-1],v=s[t--];
			H[u].push_back({v,dis[v]});
		}
		if(s[t]!=l)
		{
			H[l].push_back({s[t],dis[s[t]]});
			s[t]=l;
		}
		s[++t]=h[i];
	}
	while(t>1)
	{
		int u=s[t-1],v=s[t--];
		H[u].push_back({v,dis[v]});
	}
}

例题​

洛谷 P2495 [SDOI2011] 消耗战​

洛谷 P2495 [SDOI2011] 消耗战

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

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

代码（2）
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=250005;
const int inf=0x3f3f3f3f;
vector<pair<int,int>> G[N];
int fa[N],dep[N],siz[N],son[N];
int top[N],dfn[N],dis[N];
int cnt=0;
void dfs1(int u)
{
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(auto [v,w]:G[u])
	{
		if(v==fa[u])continue;
		fa[v]=u;
		dis[v]=min(dis[u],w);
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int e)
{
	top[u]=e;
	dfn[u]=++cnt;
	if(son[u])dfs2(son[u],e);
	for(auto [v,w]:G[u])
	{
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
bool cmp(int u,int v)
{
	return dfn[u]<dfn[v];
}
vector<pair<int,int>> H[N];
int h[N<<1];
bool tag[N];
ll dp(int u)
{
	ll res=0;
	for(auto [v,w]:H[u])
	{
		ll t=dp(v);
		res+=tag[v]?w:min(ll(w),t);
	}
	H[u].clear();
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	dis[1]=inf;
	dfs1(1);
	dfs2(1,1);
	int m;
	cin>>m;
	while(m--)
	{
		int k;
		cin>>k;
		for(int i=1;i<=k;i++)
		{
			cin>>h[i];
			tag[h[i]]=1;
		}
		sort(h+1,h+k+1,cmp);
		for(int i=1;i<k;i++)h[k+i]=lca(h[i],h[i+1]);
		h[k<<=1]=1;
		sort(h+1,h+k+1,cmp);
		k=unique(h+1,h+k+1)-h-1;
		for(int i=1;i<k;i++)
		{
			int u=lca(h[i],h[i+1]),v=h[i+1];
			H[u].push_back({v,dis[v]});
		}
		cout<<dp(1)<<'\n';
		for(int i=1;i<=k;i++)tag[h[i]]=0;
	}
	return 0;
}