这题的dp思想还是比较容易想的，关键是如何保证时间复杂度，这时就用到了虚树的技巧。
1.虚树是什么？（虚树的性质）
不妨设现在询问给出了\(k\)个点，我们命名这些节点为关键节点。
那么在我的建边方式中，虚树就是：
- 仅包括这些关键节点、它们两两之间的\(lca\)以及原树的根的一棵有向树。
- 但仍然保持原树的形态和祖先关系。即若关键节点\(a\)在原树中是关键节点\(b\)的祖先，则在虚树中，\(a\)仍是\(b\)的祖先。（这里的祖先包括父亲）
故只要我们按这个方法建出虚树，就会有：\(\text{虚树的点数}<=2\times k\)。不太严谨的证明：我们将其按\(dfn\)排序，那么相邻点的\(lca\)一定比较远点的\(lca\)深，也就是更接近那两个点。那么这样最多也就会新加入一个\(lca\),所以总共最多就\(2\times k\)个点。
2.怎么建虚树？
我们先将原树的\(dfn\)预处理出来，然后我们把所有的关键节点按\(dfn\)序排序。排完序后按顺序一个一个插入（接下来讲的\(insert()\)函数）。
同时我们也需要维护一个\(stack\)，初始只有一个点\(root\)（\(1\)号节点），\(top=1\)。
这个栈用来维护什么呢？不妨设我们现在\(insert(u)\)。那么我们把\(insert(u)\)函数执行完后，需要保证这个栈的栈顶是\(u\)，然后维护的是原树中从根到栈顶（\(u\)）路径上需要加入虚树的节点，或者也可以理解为虚树中从根到栈顶（u）的路径上的点，所以若把这个栈中的点依次两两连起边来，便是一条链，但是现在还未连边。而且我们需要保证除了栈中的点之间的连边之外，已经\(insert\)的点之间的连边都已连好了。
不妨设我们现在要\(insert(u)\)，那么我们先求出\(lca(u,st[top])\)，然后我们设原来的栈长什么样：
\(stack=\{1,...,st[k-1],st[k],...,st[top]\}\)。
然后我们找到\(lca\)在这条链中的位置，即\(deep[st[k-1]]<deep[lca]\leqslant deep[st[k]]\)，那么\(st[k]\)、\(st[k+1]\)...\(st[top]\)必然是\(lca\)的子/孙（因为\(lca\)是\(st[top]\)和\(u\)的祖先）。
那么我们考虑新建出来的栈长什么样：\(stack=\{1,...,st[k-1],lca,u\}\)。
所以我们需要\(lca\)、\(st[k]\)、\(st[k+1]\)、…、\(st[top]\)连起来并弹出栈。
然后再将\(lca\)和\(u\)入栈。
最后\(insert\)完所有点后，我们将栈中剩下的点连起来并清空栈。
为什么要按\(dfn\)排序？因为按\(dfn\)排序后，对于相邻的两个关键节点\(a\)、\(b\)，\(lca(a,b)\)一定比\(a\)和其它点的\(lca\)深度深，这样能保证建的点和边不重不漏。
然后看代码：
void insert(int u)
{
if(top==1)//特判top=1
{
if(st[top]!=u)st[++top]=u;//特判u=1
return;
}
int lca=LCA(u,st[top]);
for(;top>1&&dfn[st[top-1]]>=dfn[lca];top--)//建边，因为stack中存的是一条链，所以dfn[st[top-1]]>=dfn[lca]其实和deep[st[top-1]]>=deep[lca]是等价的
add_edge(st[top-1],st[top]);
//做完上面这段循环后，能保证dfn[st[top-1]]<dfn[lca]<=dfn[st[top]]
if(st[top]!=lca)//判断一下，防止自环
{
add_edge(lca,st[top]);
st[top]=lca;
}
st[++top]=u;
}
不理解？来看图模拟一下：
不妨设现在\(k=5\)，关键节点为\(4\)、\(7\)、\(9\)、\(10\)、\(13\)（已标红），\(stack=\{1\}\)。
然后我们要先\(insert(4)\)，发现\(top=1\)，于是\(stack=\{1,4\}\)。
然后\(insert(7)\)，发现\(lca(7,4)=1\)，于是建边\((1,4)\)，\(stack=\{1,7\}\)。
然后\(insert(9)\)，发现\(lca(7,9)=6\)，于是建边\((6,7)\)，\(stack=\{1,6,9\}\)。
然后\(insert(10)\)，发现\(lca(9,10)=9\)，于是\(stack=\{1,6,9,10\}\)。
然后\(insert(13)\)，发现\(lca(10,13)=8\)，于是建边\((9,10)\)、\((8,9)\)，\(stack=\{1,6,8,13\}\)。
最后将栈清空：建边\((8,13)\)、\((6,8)\)、\((1,6)\)，\(stack=\{\}\)。
所以建出来的虚树长这个样：
现在应该理解了吧
然后我们可以做一点小优化：若关键节点\(a\)是关键节点\(b\)的祖先，那么显然只要让\(a\)和根断掉，\(b\)就绝对会和根断掉，所以我们可以忽略\(b\)。
3.怎么dp？
不妨设\(minn[u]\)为原树中从根节点到\(u\)路径上的边权最小值，\(dp[u]\)为把以\(u\)根节点的子树中的所有关键节点都与根节点切断的最小代价。
那么要么是在\(u\)的子树中就切断，或者自己切断：
\[dp[u]=min(\sum_{v=son[u]}dp[v],minn[u]) \]那么直接树形\(dp\)就好了。
代码如下：
#include<bits/stdc++.h>
#define LN 18
#define N 250010
#define ll long long
#define INF 0x7fffffffffffffff
using namespace std;
struct Tree
{
int cnt,head[N],nxt[N<<1],to[N<<1],w[N<<1];
void init()
{
cnt=0;
memset(head,0,sizeof(head));
}
void adde(int u,int v,int c=0)
{
to[++cnt]=v;
w[cnt]=c;
nxt[cnt]=head[u];
head[u]=cnt;
}
}e1,e2;
int n,m,idx;
int top,st[N];
int a[N];
int d[N],dfn[N],fa[N][LN];
ll minn[N],dp[N];
void dfs(int u)
{
dfn[u]=++idx;
for(int i=1;i<=17;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=e1.head[u];i;i=e1.nxt[i])
{
int v=e1.to[i];
if(v!=fa[u][0])
{
fa[v][0]=u;
d[v]=d[u]+1;
minn[v]=min(minn[u],(ll)e1.w[i]);
dfs(v);
}
}
}
int LCA(int a,int b)
{
if(d[a]<d[b])swap(a,b);
for(int i=17;i>=0;i--)
if(d[fa[a][i]]>=d[b])
a=fa[a][i];
if(a==b)
return a;
for(int i=17;i>=0;i--)
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
bool cmp(int a,int b)
{
return dfn[a]<dfn[b];
}
void insert(int u)
{
if(top==1)
{
if(u!=1)st[++top]=u;
return;
}
int lca=LCA(u,st[top]);
if(lca==st[top])
return;
for(;top>1&&dfn[st[top-1]]>=dfn[lca];top--)
e2.adde(st[top-1],st[top]);
if(st[top]!=lca)
{
e2.adde(lca,st[top]);
st[top]=lca;
}
st[++top]=u;
}
void dfs2(int u)
{
if(!e2.head[u])
{
dp[u]=minn[u];
return;
}
dp[u]=0ll;
for(int i=e2.head[u];i;i=e2.nxt[i])
{
int v=e2.to[i];
dfs2(v);
dp[u]+=dp[v];
}
dp[u]=min(dp[u],minn[u]);
e2.head[u]=0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e1.adde(u,v,w),e1.adde(v,u,w);
}
d[1]=1,minn[1]=INF;
dfs(1);
scanf("%d",&m);
while(m--)
{
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++)
scanf("%d",&a[i]);
sort(a+1,a+k+1,cmp);
e2.cnt=0;
st[top=1]=1;
for(int i=1;i<=k;i++)
insert(a[i]);
for(;top>1;top--)
e2.adde(st[top-1],st[top]);
dfs2(1);
printf("%lld\n",dp[1]);
}
return 0;
}