wa+tle0pts,样例通过
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
int n,m,s=1,k,dfn[250005],ans[250005];
bool dr[250005];
vector<int> q;
bool cmp(int x, int y)
{
return dfn[x]<dfn[y];//按时间戳排序
}
int head[250005],cnt,head1[250005],cnt1;
struct dck
{
int nxt,to,ed;
} a[500005],b[500005];
void add(int x,int y,int w)
{
a[++cnt].nxt=head[x];
head[x]=cnt;
a[cnt].ed=w;
a[cnt].to=y;
}
void add2(int x,int y,int w)//虚树加边
{
b[++cnt1].nxt=head1[x];
head1[x]=cnt1;
b[cnt1].ed=w;
b[cnt1].to=y;
}
int f[250005][20],dep[250005],dp[250005][25];//f为祖先,dp为链上的最小值,dep为深度
void dfs1(int now,int fa,int id)//预处理lca
{
dfn[now]=id;
f[now][0]=fa;
dep[now]=dep[fa]+1;
for (int i=1;i<=19; i++)
{
f[now][i]=f[f[now][i-1]][i-1];
}
for (int i=head[now]; i; i=a[i].nxt)
{
if (a[i].to==fa) continue;
dp[a[i].to][0]=a[i].ed;
dfs1(a[i].to,now,++id);
}
}
void dfs2(int now,int fa)//求解答案
{
for (int i=head1[now]; i; i=b[i].nxt)
{
if (b[i].to==fa) continue;
dfs2(b[i].to,now);
if (dr[b[i].to]) ans[now]+=b[i].ed;
else ans[now]+=min(ans[b[i].to],b[i].ed);
}
}
int ww;
int lca(int x,int y)
{
bool ok=0;
ww=0x3f3f3f3f3f;
if (dep[x]>dep[y])
{
swap(x,y);
ok=1;
}
int tep=dep[y]-dep[x];
for (int j=0; tep; j++,tep>>=1)
{
if (tep&1)
{
if (!ok)//只求时间戳更大的一边的贡献
{
ww=min(ww,dp[y][j]);
}
y=f[y][j];
}
}
if (y==x) return x;
if (ok) swap(x,y);
for (int j=19; j>=0&&y!=x; j--)
{
if (f[x][j]!=f[y][j])
{
ww=min(ww,dp[y][j]);
x=f[x][j];
y=f[y][j];
}
}
ww=min(dp[y][0],ww);
return f[x][0];
}
int main()
{
memset(dp,0x3f,sizeof(dp));
n=read();
for (int i=1; i<n; i++)
{
int x,y,z;
x=read(),y=read(),z=read();
add(x,y,z);
add(y,x,z);
}
dfs1(s,0,1);
for (int i=1; i<=19; i++)
{
for (int j=1; j<=n; j++)
{
dp[j][i]=min(dp[f[j][i-1]][i-1],dp[j][i-1]);//预处理倍增最小值
}
}
m=read();
for (int pp=1; pp<=m; pp++)
{
memset(dr,0,sizeof(dr));
memset(ans,0,sizeof(ans));
memset(head1,0,sizeof(head1));
q.clear();
k=read();
for (int j=1; j<=k; j++)//二次排序+lca连边
{
int li;
li=read();
dr[li]=1;
q.push_back(li);
}
sort(q.begin(),q.end(),cmp);
int nde=q.size();
for (int i=1; i<nde; i++) q.push_back(lca(q[i-1],q[i]));
q.push_back(1);
sort(q.begin(),q.end(),cmp);
q.erase(unique(q.begin(),q.end()),q.end());
int dba=q.size();
for (int i=1;i<dba; i++)
{
int ll=lca(q[i-1],q[i]);
add2(ll,q[i],ww);
}
dfs2(1,0);//树形dp
write(ans[1]);
printf("\n");
}
}