1-C24 虚树 P2495 [SDOI2011] 消耗战

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2.5e5+10;
int n,m,k,a[N],tsp,dfn[N],dep[N],D,st[N][20],siz[N],sta[N],top;
LL mn[N];    //mn[x]:从根到x的最小边权
vector<pair<int,LL>>G[N];
vector<int>G2[N];
void dfs(int x, int xfa)
{
	dfn[x]=++tsp;
	dep[x]=dep[xfa]+1;
	st[x][0]=xfa;for(int i=1; i<=D; i++)st[x][i]=st[st[x][i-1]][i-1];
	for(auto i:G[x])if(i.first!=xfa)
	{
		int y=i.first;LL c=i.second;
		mn[y]=min(mn[x],c);
		dfs(y,x);
	}
}
int LCA(int x, int y)
{
	if(dep[x]<dep[y])swap(x, y);
	for(int i=D; i>=0; i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
	if(x==y) return y;
	for(int i=D; i>=0; i--)if(st[x][i]!=st[y][i])x=st[x][i], y=st[y][i];
	return st[x][0];
}
bool cmp(int a,int b){return dfn[a]<dfn[ b ];}
void build()
{
	sort(a+1,a+k+1,cmp);
	sta[top=1]=1;sta[++top]=a[1];
	for(int i=2; i<=k; i++) 
	{
		int lca=LCA(a[i],sta[top]);
		if(lca==sta[top]) continue;//若查询点有上下级关系，只保留离点1最近的点。
		while(top>1 && !(dep[sta[top-1]]<dep[lca]) ) G2[sta[top-1]].push_back(sta[top]), top--;
		if(lca!=sta[top]) G2[lca].push_back(sta[top]),top--, sta[++top]=lca;
		sta[++top]=a[i];
	}
	for(int i=1;i<top;i++) G2[sta[i]].push_back(sta[i+1]);
}
LL DP(int x)
{
	if(G2[x].size()==0) return mn[x]; //叶子
	LL sum=0;
	for(auto y:G2[x])
		sum+=DP(y);
	G2[x].clear();
	return min(sum,mn[x]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x,y,z; i<n; i++) 
	{
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back({y,z});G[y].push_back({x,z});
	}
	mn[1]=1e18;dep[0]=0;D=log2(n);dfs(1,0);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&k);for(int i=1; i<=k; i++) scanf("%d",&a[i]);
		build();
		printf("%lld\n",DP(1));
	}
	return 0;
}