50pts球跳

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 254514
#define int long long
struct sd{
	int y,z;
	bool operator<(sd p)const{
		return z<p.z;
	}
};
int n,m;
vector<sd> v[N],g[N];
int fa[N][25],dep[N];
int dfn[N],id;
int mini[N][25];
int gj[N];
int vis[N];
long long dp[2][N];
sd a[N],b[2*N];
void dfs(int x,int f){
	fa[x][0]=f;
	dep[x]=dep[f]+1;
	dfn[x]=++id;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i].y==f)continue;
		dfs(v[x][i].y,x);
		mini[v[x][i].y][0]=v[x][i].z;
	}
}int lca(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);
	}while(dep[x]!=dep[y]){
		y=fa[y][signed(log2(dep[y]-dep[x]))];
	}int d=log2(dep[x]);
	while(d>=0){
		if(fa[x][d]!=fa[y][d]){
			x=fa[x][d];
			y=fa[y][d];
		}d--;
	}if(x==y){
		return x;
	}else{
		return fa[x][0];
	}
}int getmin(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);
	}int minx=1e9;
	while(x!=y){
		int d=log2(dep[y]-dep[x]);
		minx=min(minx,mini[y][d]);
		y=fa[y][d];
	}return minx;
}void check(int x){
	if(vis[x]!=id){
		g[x].clear();
		vis[x]=id;
	}
}void DP(int x){
	if(gj[x]==id){
		dp[0][x]=dp[1][x]=1e9;
		return;
	}dp[0][x]=dp[1][x]=0;
	check(x);
	for(int i=0;i<g[x].size();i++){
		DP(g[x][i].y);
		dp[0][x]+=g[x][i].z;
		dp[1][x]+=min(dp[0][g[x][i].y],dp[1][g[x][i].y]);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}dfs(1,1);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
			mini[i][j]=min(mini[i][j-1],mini[fa[i][j-1]][j-1]);
		}
	}cin>>m;
	for(id=1;id<=m;id++){
		int k;
		cin>>k;
		k++;
		a[1].y=a[1].z=1;
		for(int i=2;i<=k;i++){
			cin>>a[i].y;
			a[i].z=dfn[a[i].y];
			gj[a[i].y]=id;
		}sort(a+1,a+k+1);
		int c=0;
		for(int i=1;i<k;i++){
			b[++c]=a[i];
			int l=lca(a[i].y,a[i+1].y);
			b[++c]={l,dfn[l]};
		}b[++c]=a[k];
		sort(b+1,b+c+1);
		int p=0;
		for(int i=1;i<=c;i++){
			if(b[i].y!=b[i-1].y){
				b[++p]=b[i];
			}
		}c=p;
		for(int i=1;i<c;i++){
			int l=lca(b[i].y,b[i+1].y);
			check(l);
			g[l].push_back({b[i+1].y,getmin(l,b[i+1].y)});
		}DP(1);
		cout<<min(dp[0][1],dp[1][1])<<"\n";
	}
	return 0;
}