很明显，20%=mincut 40%=每次暴力树形dp
那么正解是什么呢？不难发现∑ki<=500000,也就是每次询问的复杂度都要跟k有关
从树形dp工作的角度来看，确实有很多点我们根本就没必要访问，我们设每次要割断的岛屿为关键点
这里引入了一个新的东西叫做虚树，简单来说就是把树上没用的点去掉收缩成一棵树
具体来说，如果一个点的子树中至多只有一棵子树包含关键点，那么这个点就可以删掉
也就是说只有关键点和他们的lca会被保留下来就行了，证明总点数<=2*k-1
那么怎么构建虚树？我们先按dfs序排序，然后按这个顺序不断加点维护虚树上最新的路径
感觉建树的方法只可意会不可言传，具体见代码吧……
type node=record
len,po,next:longint;
end; var e:array[..] of node;
anc:array[..,..] of longint;
b,d,p,c,fa,st,a:array[..] of longint;
f:array[..] of int64;
v:array[..] of boolean;
w,s,m,h,t,n,len,i,x,y,z:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r: longint);
var i,j,x:longint;
begin
i:=l;
j:=r;
x:=b[a[(l+r) shr ]];
repeat
while b[a[i]]<x do inc(i);
while x<b[a[j]] do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; procedure add(x,y,z:longint);
begin
inc(len);
e[len].po:=y;
e[len].len:=z;
e[len].next:=p[x];
p[x]:=len;
end; procedure dfs(x:longint);
var i,y:longint;
begin
inc(t);
b[x]:=t; //dfs序
for i:= to h do
begin
y:=anc[x,i-];
if y<> then anc[x,i]:=anc[y,i-]
else break;
end;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if fa[x]<>y then
begin
fa[y]:=x;
anc[y,]:=x;
c[y]:=min(c[x],e[i].len); //c[]表示把这个点和根节点割开最小代价
d[y]:=d[x]+;
dfs(y);
end;
i:=e[i].next;
end;
end; function lca(x,y:longint):longint;
var i,p:longint;
begin
if d[x]<d[y] then swap(x,y);
p:=trunc(ln(d[x])/ln());
if d[x]>d[y] then
for i:=p downto do
if d[x]- shl i>=d[y] then x:=anc[x,i];
if x=y then exit(x);
for i:=p downto do
if (anc[y,i]<>anc[x,i]) then
begin
x:=anc[x,i];
y:=anc[y,i];
end;
exit(fa[x]);
end; procedure dp(x:longint); //dp过程很简单
var i,y:longint;
s:int64;
begin
if x= then f[]:=*
else f[x]:=c[x];
i:=p[x];
s:=;
while i<> do
begin
y:=e[i].po;
dp(y);
s:=s+f[y];
i:=e[i].next;
end;
p[x]:=;
if (s<>) then
if f[x]>s then f[x]:=s;
end; begin
readln(n);
h:=trunc(ln(n)/ln());
for i:= to n- do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
c[]:=;
dfs();
readln(m);
fillchar(p,sizeof(p),);
while m> do
begin
dec(m);
read(s);
for i:= to s do
read(a[i]); sort(,s);
w:=;
for i:= to s do
if lca(a[w],a[i])<>a[w] then //这里一点点优化，如果存在祖先关系的关键点，肯定割祖先以上的边
begin
inc(w);
a[w]:=a[i];
end;
len:=;
st[]:=;
t:=;
for i:= to w do
begin
x:=a[i];
z:=lca(x,st[t]);
while d[z]<d[st[t]] do //这里画个图比较好理解，类似一个新路径和原来维护的路径的一个分叉
begin
if d[z]>=d[st[t-]] then
begin
add(z,st[t],);
dec(t);
if st[t]<>z then
begin
inc(t);
st[t]:=z;
end;
break;
end;
add(st[t-],st[t],); //把原来分叉的那段建出来
dec(t);
end;
if st[t]<>x then
begin
inc(t);
st[t]:=x;
end;
end;
while t> do //把维护的路径建出来
begin
add(st[t-],st[t],);
dec(t);
end;
dp();
writeln(f[]);
end;
end.