虚树 （模板）

[SDOI2011] 消耗战 - 洛谷

虚树，就是用来在图上dp时，避免无用的点太多影响时间的一种优化方式，它新建了一张图，从而减少无关点的遍历，在稀疏图上时能大大优化时间。

具体做法就是，把所有关键点按dfs序排序，然后一条链一条链地遍历，其中会出现4中情况，参考大佬博客：题解 P2495 【[SDOI2011]消耗战】 - Rhodoks 的博客 - 洛谷博客 

我们按照栈来遍历就正好符合由一条链跳到另一条链的过程，叶节点先出栈，根节点不变，再入新的链，按照不同情况连点，目的是保证这些关键点互相连接。

参考代码：

/*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl "\n"
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double E = exp(1);
const double PI = acos(-1.0);
const int mod=1e9+7; 
const int maxn=250010;
struct node{
	int to,nxt,w;
}e[maxn<<1];int tot,head[maxn]; 
void add(int x,int y,int z){ e[++tot]={y,head[x],z};head[x]=tot;}
int dep[maxn],fa[maxn],siz[maxn],son[maxn],top[maxn],mi[maxn];
void dfs1(int x,int f){
	dep[x]=dep[f]+1;
	fa[x]=f; 
	siz[x]=1;
	int mson=-1;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(f==v) continue;
		mi[v]=min(mi[x],e[i].w);
		dfs1(v,x);
		siz[x]+=siz[v];
		if(siz[v]>mson) son[x]=v,mson=siz[v];
	}
}
int dfn[maxn],id;
void dfs2(int x,int t){
	top[x]=t;
	dfn[x]=++id;
	if(!son[x]) return ;
	dfs2(son[x],t);
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa[x]||v==son[x]) continue;
		dfs2(v,v);
	}
}
int lca(int x,int y){
	while(top[x]!=top[y])dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
	return dep[x]<dep[y]?x:y;
}
int n,m,k,a[maxn],s[maxn],h;
vector<int>g[maxn];
void add_g(int x,int y){g[x].push_back(y);}
void _insert(int x){
	if(h==1){ s[++h]=x;return;}
	int tep=lca(x,s[h]);
	if(tep==s[h])return ;//情况1 
	while(h>1&&dfn[s[h-1]]>=dfn[tep])add_g(s[h-1],s[h]),h--;// 情况4化为2，3 
	if(tep!=s[h])add_g(tep,s[h]),s[h]=tep;//情况2，3 
	s[++h]=x;// 虚树建树 
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
int dp(int x,int fa){
	if(g[x].size()==0) return mi[x];
	int sum=0;
	for(auto y:g[x]) sum+=dp(y,x);
	g[x].clear();
	return min(sum,mi[x]);
}
signed main(){
	fast
	cin>>n;
	mi[1]=1e17;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);add(y,x,z);
	}
	dfs1(1,0);dfs2(1,1);
	cin>>m;
	for(int i=1;i<=m;i++){
		int k;cin>>k;
		for(int j=1;j<=k;j++) cin>>a[j];
		sort(a+1,a+1+k,cmp);
		h=1;s[h]=1;
		for(int j=1;j<=k;j++)_insert(a[j]);
		while(h>0) add_g(s[h-1],s[h]),h--;
		cout<<dp(1,0)<<endl;
	}
}