30分 求条

#include<bits/stdc++.h>
#define int long long
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=5.5*1e5+5;
int n,m,tree[N<<2],id[N],fa[N],tot[N],dep[N],siz[N],son[N],cnt,p[N],h[N],t[N]; 
struct node{
	int x,w;
};
vector<node>a[N];
vector<int>b[N];
void Qxiu(int l,int r,int left,int right,int id,int f){
	if(left<=l&&r<=right){
		tree[id]=f;
		return ;
	}
	int mid=l+r>>1;
	if(left<=mid)Qxiu(l,mid,left,right,ls,f);
	if(mid<right)Qxiu(mid+1,r,left,right,rs,f);
	tree[id]=min(tree[ls],tree[rs]);
}
int val;
void Qzo(int l,int r,int left,int right,int id){
	if(id==1)val=1e17;
	if(left<=l&&r<=right){
		val=min(val,tree[id]);
		return ;
	}
	int mid=l+r>>1;
	if(left<=mid)Qzo(l,mid,left,right,ls);
	if(mid<right)Qzo(mid+1,r,left,right,rs);
}
void dfs1(int x){
	siz[x]=1;
	dep[x]=dep[fa[x]]+1;
	for(int i=0;i<a[x].size();i++){
		if(a[x][i].x==fa[x])continue;
		fa[a[x][i].x]=x;
		dfs1(a[x][i].x);
		siz[x]+=siz[a[x][i].x];
		if(siz[son[x]]<siz[a[x][i].x])son[x]=a[x][i].x;
	}
}
void dfs2(int x,int fg){
	id[x]=++cnt;
	tot[x]=fg;
	if(!son[x])return;
	dfs2(son[x],fg);
	for(int i=0;i<a[x].size();i++){
		if(a[x][i].x==fa[x])continue;
		if(a[x][i].x==son[x]){
			Qxiu(1,n,id[son[x]],id[son[x]],1,a[x][i].w);continue;
		}
		dfs2(a[x][i].x,a[x][i].x);
		Qxiu(1,n,id[a[x][i].x],id[a[x][i].x],1,a[x][i].w);
	}
}
int LCA(int x,int y){
	while(tot[x]!=tot[y]){
		if(dep[tot[x]]<dep[tot[y]])swap(x,y);
		x=fa[tot[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
int Lca(int x,int y){
	int now=1e17;
	while(tot[x]!=tot[y]){
		if(dep[tot[x]]<dep[tot[y]])swap(x,y);
		val=1e17;
		Qzo(1,n,id[tot[x]],id[x],1);
		now=min(now,val);
		x=fa[tot[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	val=1e17;
	if(id[x]+1<=id[y]){
		
		Qzo(1,n,id[x]+1,id[y],1);
	}
	return min(now,val);
}
bool cmp(int x,int y){
	return id[x]<id[y];
}
int dp[N];
void dfs(int x,int ft){
	dp[x]=0;
	for(int i=0;i<b[x].size();i++){
		if(b[x][i]==ft)continue;
		dfs(b[x][i],x);
		if(t[b[x][i]]){
			dp[x]+=Lca(b[x][i],x);
		}
		else{
			dp[x]+=min(dp[b[x][i]],Lca(b[x][i],x));
		}
	}
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,w;cin>>u>>v>>w;
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
	dfs1(1);
	dfs2(1,1);
	cin>>m;
	while(m--){
		int num=0,k;cin>>k;
		for(int i=1;i<=k;i++)cin>>h[i],t[h[i]]=1;
		sort(h+1,h+1+k,cmp);
		p[++num]=1;p[++num]=h[k];
		for(int i=1;i<k;i++){
			p[++num]=h[i];
			p[++num]=LCA(h[i],h[i+1]);
		}
		sort(p+1,p+1+num,cmp);
		for(int i=2;i<=num;i++){
			if(p[i]==p[i-1])continue;
			int lca=LCA(p[i],p[i-1]);
			b[p[i]].push_back(lca);
			b[lca].push_back(p[i]);
		}
		dfs(1,1);
		cout<<dp[1]<<"\n";
		for(int i=2;i<=num;i++){
			t[h[i]]=0;
			if(p[i]==p[i-1])continue;
			int lca=LCA(p[i],p[i-1]);
			b[p[i]].pop_back();
			b[lca].pop_back();
		}
	}
	return 0;
}