题目
题解

Solution

首先把询问点根据原树 d f s dfs dfs序排序，显然这些点都要出现在虚树中来，而且为了保证结构不被破坏，另外一些跟他们有关系的点都要加入到虚树中来
我们用一个栈维护原树上的一条链，自栈底到栈顶，深度由小变大
每次考虑插入询问点进栈
如果插入点的祖先是栈顶元素，那么直接插入即可，因为反正是一条链上的结点
如果不是的话，那么只有可能分居他们的 l c a lca lca的两棵子树中
如果栈顶元素的下一位的深度比 l c a lca lca深，那么我们需要不断弹出栈顶元素，并且在弹出之前与栈顶下一位连一下边，直到 l c a lca lca深度比栈顶元素深，此时把 l c a lca lca加入栈，把需要插入的点加入栈，继续往下处理。又因为我们是按 d f s dfs dfs序做的，这样就可以保证我们开始说的，维护的是树上的一条链。之后再 d p dp dp就可以了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=250002;
struct node{
	int to,ne,w;
}e[N*2];
int x,y,z,i,tot,cnt,h[N],head[N],id[N],fa[N][18],top,st[N],dep[N],n,m,val[N],k,q[N];
ll f[N];
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for(;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for(;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
inline void wri(ll a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(ll a){wri(a),puts("");}
void add(int x,int y,int z){e[++tot]=(node){y,h[x],z},h[x]=tot;}
bool cmp(int x,int y){return id[x]<id[y];}
void link(int x,int y){if (x!=y) add(x,y,0);}
int LCA(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=17;~i;i--)
		if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if (x==y) return x;
	for (int i=17;~i;i--)
		if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void dfs(int u,int f){
	fa[u][0]=f,id[u]=++tot;
	for (int i=1;i<18;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=f) dep[v]=dep[u]+1,val[v]=min(val[u],e[i].w),dfs(v,u);
}
void dp(int u){
	f[u]=val[u];
	ll s=0;
	for (int i=h[u],v;i;i=e[i].ne) dp(v=e[i].to),s+=f[v];
	h[u]=0;
	if (u==1 || s && s<f[u]) f[u]=s;//u=1时f的初值要赋得很大，而val[1]=1e9，太小了，所以手动赋值一下
}
void solve(){
	k=rd();
	for (int i=1;i<=k;i++) q[i]=rd();
	sort(q+1,q+k+1,cmp);
	cnt=1,tot=0;
	for (int i=2;i<=k;i++)
		if (LCA(q[i],q[cnt])!=q[cnt]) q[++cnt]=q[i];
	st[++top]=1;
	for (int i=1;i<=cnt;i++){
		int t=q[i],lca=0;
		while (top){
			lca=LCA(st[top],t);
			if (top>1 && dep[lca]<dep[st[top-1]]) link(st[top-1],st[top]),top--;
			else{
				if (dep[lca]<dep[st[top]]) link(lca,st[top]),top--;
				break;
			}
		}
		if (st[top]!=lca) st[++top]=lca;
		st[++top]=t;
	}
	top--;
	while (top) link(st[top],st[top+1]),top--;
	dp(1);
	wln(f[1]);
}
int main(){
	n=rd();
	for (i=1;i<n;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z);
	val[1]=1e9,tot=0,dep[0]=-1,dfs(1,0);
	memset(h,0,(n+1)<<2);
	m=rd();
	for (;m--;) solve();
}