文件详细信息

下载本文件

本文件的大小为 2532 字节。

#include<algorithm>
#include<cstdio>
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
void swap(int&a,int&b){
	int temp=a;
	a=b;
	b=temp;
}
template<typename T>T min(T a,T b){
	return a<b?a:b;
}
const int maxn=250005;
int n,u,v,w;
int m,k,h[maxn];
int log[maxn];
namespace origin{
	int total,head[maxn],to[maxn<<1],next[maxn<<1],len[maxn<<1];
	int dfn[maxn];
	long long minv[maxn];
	int dfncnt;
	void add(int a,int b,int c){
		to[++total]=b;
		next[total]=head[a];
		head[a]=total;
		len[total]=c;
	}
	int depth[maxn],fa[maxn][20];
	void dfs(int u,int from){
		dfn[u]=++dfncnt;
		depth[u]=depth[from]+1;
		fa[u][0]=from;
		for(int i=1;i<=log[depth[u]];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
		for(int i=head[u];i;i=next[i]){
			int v=to[i];
			if(v==from)continue;
			minv[v]=min(minv[u],(long long)len[i]);
			dfs(v,u);
		}
	}
	int lca(int x,int y){
		if(depth[x]<depth[y])swap(x,y);
		while(depth[x]>depth[y])x=fa[x][log[depth[x]-depth[y]]];
		if(x==y)return x;
		for(int i=log[depth[x]];i>=0;i--)
			if(fa[x][i]!=fa[y][i])
				x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
}
bool query[maxn];
bool cmp(int a,int b){
	return origin::dfn[a]<origin::dfn[b];
}
int stack[maxn],top;
namespace virt{
	int total,head[maxn],to[maxn<<1],next[maxn<<1];
	void add(int a,int b){
		to[++total]=b;
		next[total]=head[a];
		head[a]=total;
	}
	long long dp(int u){
		long long sum=0,answer;
		for(int i=head[u];i;i=next[i])sum+=dp(to[i]);
		if(query[u])answer=origin::minv[u];
		else answer=min(sum,origin::minv[u]);
		query[u]=false;
		head[u]=0;
		return answer;
	}
}
int main(){
	register int i;
	n=read();
	for(i=2;i<=n;i++)log[i]=log[i-1]+((i&(i-1))==0);
	for(i=1;i<n;i++){
		u=read(),v=read(),w=read();
		origin::add(u,v,w),origin::add(v,u,w);
	}
	origin::minv[1]=0x3f3f3f3f3f3f3f3f;
	origin::dfs(1,0);
	m=read();
	while(m--){
		virt::total=0;
		k=read();
		for(i=1;i<=k;i++)query[h[i]=read()]=true;
		std::sort(h+1,h+k+1,cmp);
		stack[top=1]=h[1];
		for(i=2;i<=k;i++){
			int _lca=origin::lca(h[i],stack[top]);
			if(_lca!=stack[top]){
				while(origin::dfn[_lca]<origin::dfn[stack[top-1]])virt::add(stack[top-1],stack[top]),top--;
				if(origin::dfn[_lca]>origin::dfn[stack[top-1]])virt::head[_lca]=0,virt::add(_lca,stack[top]),stack[top]=_lca;
				else virt::add(_lca,stack[top--]);
			}
			virt::head[h[i]]=0,stack[++top]=h[i];
		}
		for(i=1;i<top;i++)virt::add(stack[i],stack[i+1]);
		printf("%lld\n",virt::dp(stack[1]));
	}
	return 0;
}