Description：

给一棵有边权的树，多次询问把其中 $k$ 个关键点和 $1$ 号节点断开的最小代价。

$1\leqslant n\leqslant 250000,\sum k\leqslant500000$

Solution：

首先求出 $val[k]$ 表示从根节点到 $k$ 的最小边权，即断开 $k$ 这棵子树的花费，那么就可以用一个树形 $DP$ 求出 $f[i]=\min(val[k],\sum f[son[k][i]])$ ， $f[root]$ 就是答案，但是这样单次是 $O(n)$ 的，那么可以把这 $k$ 个点的虚树建出来，然后在虚树上树形 $DP$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 250010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

int dfn[MAXN],tot = 0;

long long val[MAXN];

void dfs(int k)

{

	dfn[k] = ++tot;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			val[e[i].to] = min(val[k],(long long)e[i].v);

			dfs(e[i].to);

		}

	}

	return;

}

int fa[MAXN],siz[MAXN],son[MAXN],top[MAXN],dep[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		dfs1(e[i].to,depth + 1);

		siz[k] += siz[e[i].to];

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

		{

			son[k] = e[i].to;

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int v[MAXN];

bool cmp_dfn(int a,int b){return dfn[a] < dfn[b];}

int s[MAXN],tp = 0;

vector<int> g[MAXN];

void add(int f,int p)

{

	g[f].push_back(p);

	return;

}

int root;

long long f[MAXN];

bool tag[MAXN];

void dp(int k)

{

	long long sum = 0;

	for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

	{

		dp(*i);

		sum += f[*i];

	}

	g[k].clear();

	if(tag[k])f[k] = val[k];

	else f[k] = min(sum,(long long)val[k]);

	return;

}

int main()

{

	scanf("%d",&n);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		a = rd();b = rd();c = rd();

		add(a,b,c);

	}

	val[1] = 0x3f3f3f3f3f3f3f3f;

	dfs(1);

	dfs1(1,1);dfs2(1,1);

	scanf("%d",&m);

	while(m--)

	{

		scanf("%d",&v[0]);

		for(int i = 1;i <= v[0];++i)v[i] = rd();

		sort(v + 1,v + 1 + v[0],cmp_dfn);

		tp = 0;

		s[++tp] = 1;

		for(int i = 1;i <= v[0];++i)

		{

			tag[v[i]] = true;

			int lca = LCA(s[tp],v[i]);

			if(lca == s[tp])

			{

				s[++tp] = v[i];

				continue;

			}

			while(tp >= 2)

			{

				if(dfn[lca] < dfn[s[tp - 1]])

				{

					add(s[tp - 1],s[tp]);

					--tp;

				}

				else

				{

					add(lca,s[tp]);

					--tp;

					break;

				}

			}

			if(lca != s[tp])s[++tp] = lca;

			s[++tp] = v[i];

		}

		while(tp >= 2)

		{

			add(s[tp - 1],s[tp]);

			--tp;

		}

		root = s[tp];

		dp(root);

		printf("%lld\n",f[root]);

		for(int i = 1;i <= v[0];++i)tag[v[i]] = false;

	}

	return 0;

}