MLE救救孩子

// Problem: P2495 [SDOI2011] 消耗战
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2495
// Memory Limit: 505 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define Rep(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define Per(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
//#define min(x,y) ((x)<(y)?(x):(y))
//#define max(x,y) ((x)<(y)?(y):(x))
#define DEBUG 1
namespace FastIO{
#define isdigit(x) (x>='0'&&x<='9')
#define MAXSIZE (1<<20)
#define PREC 6
#define FileIO(fn) freopen(fn".in","r",stdin),freopen(fn".out","w",stdout)
	char buf[MAXSIZE],pbuf[MAXSIZE],*pp=pbuf,*p1,*p2;
	struct CONDES{
#if DEBUG
#else
		CONDES(){p1=buf;p2=buf;pp=pbuf;}
		~CONDES(){fwrite(pbuf,1,pp-pbuf,stdout);}
#endif
	}_CONDES;
	inline char gc(){
#if DEBUG
		return getchar();
#endif
		if(p1==p2)p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);
		return p1==p2?' ':*p1++;
	}
	template<class T>
	inline void read(T&x){
		double tmp=1;
		bool sign=0;x=0;
		char c=gc();
		for(;!isdigit(c);c=gc())if(c=='-')sign=1;
		for(;isdigit(c);c=gc())x=x*10+(c-'0');
		if(c=='.')for(c= gc();isdigit(c);c=gc())tmp/=10.0,x+=tmp*(c-'0');
		if(sign)x=-x;
	}
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
	inline void read(char *s){
		char c=gc();
		for(;blank(c);c=gc());
		for(;!blank(c);c=gc())*s++=c;
		*s=0;
	}
	inline void read(char &c){for(c=gc();blank(c);c=gc());}
	template<class T,class...Args>
	inline void read(T&x,Args&...args){read(x);read(args...);}
	inline void pc(const char &c){
#if DEBUG
		putchar(c);
#else
		if(pp-pbuf==MAXSIZE)fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;
		*pp++=c;
#endif
	}
	template<class T>
	inline void write(T x){
		if(x<0)x=-x,pc('-');
		static int sta[35];
		int top=0;
		do{sta[top++]=x%10,x/=10;}while(x);
		while(top)pc(sta[--top]+'0');
	}
	inline void write(char* s){while(*s)pc(*s++);}
	inline void write(const char* s){while(*s)pc(*s++);}
	inline void write(char c){pc(c);}
	template<class T>
	inline void write_float(T x,int prec=PREC){
		if(x==0){pc('0');pc('.');while(prec--)pc('0');return;}
		if(x<0)x=-x,pc('-');
		static int sta[35];
		int top=0;T pw=pow(10,prec);
		x=round(pw*x);
		if(x<pw)pc('0'),pc('.');
		do{sta[top++]=((ull)x)%10;x=(x-(ull)x%10)/10.0;}while(x>=1.0);
		while(top){pc(sta[--top]+'0');if(top==prec)pc('.');}
	}
	template<class T,class...Args>
	inline void write(T x,Args...args){write(x);write(args...);}
};
using namespace FastIO;
#define int long long
const int N=1e6+5;
int n,m,t,st[N],tot=0,tot1=0,dcnt=0,lst[N];
struct edge{int to,nx;ll vl;}e[N<<1],e1[N<<1];
struct node{
	int dfn,hd=0,hd1=0,tp,dep,siz,fa;
	bool que=0;
	ll mv;
}a[N];
void added(int x,int y,ll z){
	tot++;
	e[tot].to=y;
	e[tot].vl=z;
	e[tot].nx=a[x].hd;
	a[x].hd=tot;
}
void added1(int x,int y){
	tot1++;
	e1[tot1].to=y;
	e1[tot1].nx=a[x].hd1;
	a[x].hd1=tot1;
}
void dfs(int x){
	int i,y,z;
	a[x].dfn=++dcnt;a[x].siz=1;
	for(i=a[x].hd;i;i=e[i].nx){
		y=e[i].to;z=e[i].vl;
		if(y==a[x].fa)continue;
		a[y].fa=x;
		a[y].dep=a[x].dep+1;
		a[y].mv=min(a[x].mv,z);
		dfs(y);
		a[x].siz+=a[y].siz;
	}
}
void dfs2(int x,int tp){
	int i,y,sn,mx=-1;
	for(i=a[x].hd;i;i=e[i].nx){
		y=e[i].to;
		if(y==a[x].fa)continue;
		if(a[y].siz>mx)mx=a[y].siz,sn=y;
	}
	for(i=a[x].hd;i;i=e[i].nx){
		y=e[i].to;
		if(y==a[x].fa)continue;
		dfs2(y,(y^sn)?y:tp);
	}
}
int getlca(int x,int y){
	while(a[x].tp!=a[y].tp){
		if(a[a[x].tp].dep<a[a[y].tp].dep)swap(x,y);
		x=a[a[x].tp].fa;
	}
	return(a[x].dep<a[y].dep)?x:y;
}
ll solve(int x){
	ll sum=0,ans;
	int i,y;
	for(i=a[x].hd1;i;i=e1[i].nx){
		y=e1[i].to;
		if(y==a[x].fa)continue;
		sum+=solve(y);
	}
	if(a[x].que)ans=a[x].mv;
	else ans=min(a[x].mv,sum);
	a[x].que=0;
	a[x].hd1=0;
	return ans;
}
bool cmp(int x,int y){return a[x].dfn<a[y].dfn;}
signed main(){
	a[1].mv=1e18;
	int i,q,x,y,nw,lc;
	ll z;
	read(n);
	for(i=1;i<n;i++){
		read(x,y,z);
		added(x,y,z);
		added(y,x,z);
	}
	dfs(1);
	read(q);
	while(q--){
		tot1=0;
		read(m);
		for(i=1;i<=m;i++){
			read(lst[i]);
			a[lst[i]].que=1;
		}
		sort(lst+1,lst+m+1,cmp);
		st[t=1]=lst[1];
		for(i=2;i<=m;i++){
			nw=lst[i];
			lc=getlca(nw,st[t]);
			while(1)
				if(a[lc].dep>=a[st[t-1]].dep){
					if(lc^st[t]){
						added1(lc,st[t]);
						if(lc!=st[t-1])st[t]=lc;
						else t--;
					}break;
				}else{
					added1(st[t-1],st[t]);  
					t--;
				}
			st[++t]=nw;
		}
		while(--t)added1(st[t],st[t+1]);
		write(solve(st[1]),'\n');
	}
	return 0;
}