虚树

参考资料

虚树 - OI Wiki

二次排序

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

单调栈

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

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

代码（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 t)
{
	top[u]=t;
	dfn[u]=++cnt;
	if(son[u])dfs2(son[u],t);
	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;
}
vector<int> H[N];
int a[N<<1];
bool tag[N];
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;
}
ll dfs(int u)
{
	ll res=0;
	for(auto v:H[u])
	{
		ll w=dis[v],t=dfs(v);
		res+=tag[v]?w:min(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>>a[i];
			tag[a[i]]=1;
		}
		k=build(k);
		cout<<dfs(1)<<'\n';
		for(int i=1;i<=k;i++)tag[a[i]]=0;
	}
	return 0;
}

#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 t)
{
	top[u]=t;
	dfn[u]=++cnt;
	if(son[u])dfs2(son[u],t);
	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;
}
vector<int> H[N];
int a[N],s[N];
bool tag[N];
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];
	}
	for(int i=1;i<t;i++)H[s[i]].push_back(s[i+1]);
}
ll dfs(int u)
{
	ll res=0;
	for(auto v:H[u])
	{
		ll w=dis[v],t=dfs(v);
		res+=tag[v]?w:min(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>>a[i];
			tag[a[i]]=1;
		}
		build(k);
		cout<<dfs(1)<<'\n';
		for(int i=1;i<=k;i++)tag[a[i]]=0;
	}
	return 0;
}

参考资料​

二次排序​

单调栈​

例题​

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

参考资料

二次排序

单调栈

例题

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