#include<cstdio>
#include<iostream>
#define M 1000009
#define N 250009
#define ll long long
#define inf 1000000000000000000LL
#include<algorithm>
using namespace std;
int n,head[N],next[M],u[M],cnt,fa[N][],deep[N],m,h[N],dfn[N],TI,cnt1,zhan[N],tot,head1[N];
int next1[M],u1[M],v[M];
ll mn[N],f[N];
void jia(int a1,int a2,int a3)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
v[cnt]=a3;
return;
}
void jia2(int a1,int a2)
{
if(a1==a2)
return;
cnt1++;
next1[cnt1]=head1[a1];
head1[a1]=cnt1;
u1[cnt1]=a2;
return;
}
void dfs(int a1)
{
dfn[a1]=++TI;
for(int i=;(<<i)<=deep[a1];i++)
fa[a1][i]=fa[fa[a1][i-]][i-];
for(int i=head[a1];i;i=next[i])
if(u[i]!=fa[a1][])
{
deep[u[i]]=deep[a1]+;
fa[u[i]][]=a1;
mn[u[i]]=min(mn[a1],(ll)v[i]);
dfs(u[i]);
}
}
bool cmp(int a1,int a2)
{
return dfn[a1]<dfn[a2];
}
int lca(int a1,int a2)
{
if(deep[a1]<deep[a2])
swap(a1,a2);
int a3=deep[a1]-deep[a2];
for(int i=;i<=;i++)
if(a3&(<<i))
a1=fa[a1][i];
for(int i=;i>=;i--)
if(fa[a1][i]!=fa[a2][i])
{
a1=fa[a1][i];
a2=fa[a2][i];
}
if(a1==a2)
return a1;
return fa[a1][];
}
void dp(int a1)
{
ll tmp=;
f[a1]=mn[a1];
for(int i=head1[a1];i;i=next1[i])
{
dp(u1[i]);
tmp+=f[u1[i]];
}
head1[a1]=;
if(tmp<f[a1]&&tmp)
f[a1]=tmp;
return;
}
void solve()
{
cnt1=;
scanf("%d",&h[]);
for(int i=;i<=h[];i++)
scanf("%d",&h[i]);
sort(h+,h+h[]+,cmp);
int tot=;
h[++tot]=h[];
for(int i=;i<=h[];i++)
if(lca(h[tot],h[i])!=h[tot])h[++tot]=h[i];
h[]=tot;
tot=;
zhan[++tot]=;
for(int i=;i<=h[];i++)
{
int f=lca(h[i],zhan[tot]);
for(;;)
{
if(deep[f]>=deep[zhan[tot-]])
{
jia2(f,zhan[tot]);
tot-=;
if(zhan[tot]!=f)
{
tot+=;
zhan[tot]=f;
}
break;
}
jia2(zhan[tot-],zhan[tot]);
tot-=;
}
if(h[i]!=zhan[tot])
{
tot+=;
zhan[tot]=h[i];
}
}
for(;tot>;jia2(zhan[tot-],zhan[tot]),tot--);
dp();
printf("%lld\n",f[]);
return;
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int a1,a2,a3;
scanf("%d%d%d",&a1,&a2,&a3);
jia(a1,a2,a3);
jia(a2,a1,a3);
}
mn[]=inf;
dfs();
scanf("%d",&m);
for(int i=;i<=m;i++)
solve();
return ;
}
显然想到DP，然而DP超时，这个题是构建虚树，然后DP。