Rt,写+调花了一个上午,现在50pts,内有注释 是利用单调栈实现的

史山警告：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector> 
#include<cstring>
#include<stack>

#define ll long long
using namespace std;

const int MAXN = 1e6+10;//注意虚树是要开两倍的点空间的 
const int MAXM = 1e6+10;
const int LGN = 25+5;
const ll INF = 0x3f3f3f3f3f;

int cnt = 0;//边的数量(链式前向星) 
int dfncnt = 0;//dfn点序 

//闲话:多测只能在dfs中清空好烦好难调 

struct Edge{
	int v,w;
};

//虚数的边 
struct Edge_Vt{
	int nxt,v,w;	
}edge[MAXN<<1]; 

//链式前向星加边 
int head[MAXN<<1];
void add(int x,int y,ll val){
	edge[++cnt].nxt = head[x];
	edge[cnt].v = y,edge[cnt].w = val;
	head[x] = cnt;
}

vector<Edge> vct[MAXN<<1];//实树的边
 

int n,q;
int dfn[MAXN],dep[MAXN];//每个点的dfn和dep 
int fa[MAXN][LGN],mxk[MAXN];//倍增lca,u节点的k级祖先是什么,以及u的最大的祖先是多少级 
ll disfa[MAXN][LGN];//表示到达k级祖先的边权最小值(因为题目中我们只需知道切断这当中的最小边权就可以切断联系) 

int Tc; 

ll dp[MAXN];//表示树型dp的方案数量 

int lst[MAXN];//关键点的列表 
bool qry[MAXN];//表示这个点是否是关键点 

stack<int> st;//虚树上维护的单调栈
//虚数维护的栈之所以是单调栈,是因为这个栈中的点满足栈顶的dfn是小于栈底的dfn序的,并且其任意时刻都是维护虚树上的一条链的 

void dfs(int u,int par){//dfs预处理 
	
	if(u != 1)dep[u] = dep[par]+1;
	else dep[u] = 1;
	dfn[u] = ++dfncnt;
	
	
	fa[u][0] = par;mxk[u] = 0;
	for(int i = 1; fa[fa[u][i-1]][i-1] ;i++) fa[u][i] = fa[fa[u][i-1]][i-1],disfa[u][i] = min(disfa[u][i-1],disfa[fa[u][i-1]][i-1]),mxk[u] = i;
	
	for(int i = 0;i < (int)vct[u].size();i++){
		int v = vct[u][i].v,w = vct[u][i].w;
		if(v == par)continue;
		disfa[v][0] = w;
		dfs(v,u);
	}
	return ;
}

ll d;//这个d是额外的更新距离的边权,d是我们到lca的边权 
int lca(int a,int b){//倍增lca的标准形式 
	d = (1ll<<35);	
	if(dep[b] > dep[a])swap(a,b);
	for(int i = mxk[a];i >= 0;i--) if(dep[fa[a][i]] >= dep[b]) d = min(d,disfa[a][i]),a = fa[a][i];
	if(a == b)return a;
	for(int i = mxk[a];i >= 0;i--) if(fa[a][i] != fa[b][i]) d = min(d,min(disfa[a][i],disfa[b][i])),a = fa[a][i],b = fa[b][i];
	d = min(d,min(disfa[a][0],disfa[b][0]));return fa[a][0];
} 

int sec_top(){//返回单调栈的次大值 (次栈顶) 
	int p = st.top(),sc_top; st.pop();
	if(st.empty())sc_top = 0;//正常来说不会进到这里,可以证明有1的情况不可能有dfn比1还小的点 
	else sc_top = st.top();
	st.push(p);return sc_top;
}
bool cmp(int a,int b) {return dfn[a] < dfn[b]; }//虚数建立前要先满足dfn序的顺序排列 

void build_Vt(int pt){//单调栈建立虚树(本质上是建立所有关键点与其Lca的虚拟树,本质是我们只关心关键点间的祖先关系和权值)
	while(!st.empty())st.pop();//还有就是这个栈每次会留下一个1,要把1也pop掉 
	sort(lst+1,lst+1+pt,cmp);//按照dfn排序维护正确性 
	st.push(1);//初始钦定根节点为关键点(大概率是有这个点的除非是所有关键点在一条链上,此时不管他就好,不影响答案)
	head[1] = 0;cnt = 0;//一开始的时候要消除上一次的边 
	for(int i = 1;i <= pt;i++){//按照dfn序列以此加入关键点
		int u = lst[i],Lca = lca(u,st.top());//这个Lca是永远落在原来维护的链与新加入点所在链的公共边上的(正确性有dfn序保证) 
		//if(u == 1)continue;
		if(Lca != st.top()){
			//进到这里面说明了,栈顶一定不存在与新的LCA的链上,那么原来链上的全部pop掉(注意这里是对原来的链连边的) 
			while(dfn[Lca] < dfn[sec_top()]){lca(sec_top(),st.top()),add(sec_top(),st.top(),d),st.pop();}//我们对次栈顶做决策(次栈顶在链上为止) 
			if(dfn[Lca] > dfn[sec_top()]){head[Lca] = 0,lca(Lca,st.top()),add(Lca,st.top(),d),st.pop(),st.push(Lca);}//说明Lca是位于原来的栈顶与次栈顶之间 
			else {lca(Lca,st.top()),add(Lca,st.top(),d),st.pop();}//这种情况下Lca就是次栈顶(dfn既不比次栈顶大又不比次栈顶小那当然是次栈顶啦) 
		}
		head[u] = 0;//清空图(这是u的第1次进栈,此时应当消除之前的影响) 
		st.push(u);
	}while(st.size() > 1){
		//cout << st.top() << " " << sec_top() << endl;
		lca(sec_top(),st.top());//注意因为这里连的都是单项边,所以我们都是要注意u,v的区分性的 
		add(sec_top(),st.top(),d);
		st.pop();//注意最后一条链自己手动连 
	} return ;
}

void trdp(int u){
	
	dp[u] = 0;//同样要清空多测带来的影响 
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].v;ll w = edge[i].w;
		trdp(v);
		if(qry[v])qry[v] = 0,dp[u] = dp[u] + w;//注意这里的时候将这些处理过的也标记0 
		else dp[u] = min(dp[v],1ll*w);
	}
} 

int main(){
	
	scanf("%d",&n);
	for(int i = 1;i < n;i++){
		int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);
		vct[u].push_back((Edge){v,w});
		vct[v].push_back((Edge){u,w});
	} 
	
	for(int i = 1;i <= n;i++)dp[i] = INF; 
	
	dfs(1,0); 
	
	scanf("%d",&q);
	while(q--){
		int pt;scanf("%d",&pt);
		for(int i = 1;i <= pt;i++){
			scanf("%d",&lst[i]);
			qry[lst[i]] = true;
		}
		
		build_Vt(pt); 
		trdp(1);
		printf("%lld\n", dp[1] );
	}
	
	return 0;
}