题意：一棵N个点的树上有若干个关键点，每条边有一个边权，现在要将这些关键点到1的路径全部切断，切断一条边的代价就是边权。
共有M组询问，每组询问有k[i]个关键点，对于每组询问求出完成任务的最小代价。
对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
思路：第一题虚树，需要详细地记录一下。
对于此题，朴素的树形DP很好理解：
dp[u]为将u子树中的关键点全部切断的最小代价
dp[u]=min(cut[u],sigma(dp[v])) 其中cut[u]为1到u中最小的边权
但因为询问有多次且需要切断的关键点不同，会超时
经过思考可以发现只有很少的点需要被作为关键点进行处理：当一个点是关键点，或者为某两个关键点的LCA时，这个点会被作为关键点
显然关键点的数量是O(n)级别的
对于每次询问重新构造一棵虚树，使用栈
现将关键点按DFS序从小到大排序
对于一条链上的点只需保留两个
设新插入的点为x，栈顶的第一个点为y，第二个点为z，x与y的LCA为w：
1.dfn[w]<dfn[z] (w,x)连边,x入栈
2.dfn[w]=dfn[z] (y,z)连边
3.dfn[w]>dfn[z] 将w加入栈，(w,z),(w,x)之间连边
const oo=;
var head,vet,next,len,head1,vet1,next1,
dep,flag,dfn,b,h,stk:array[..]of longint;
dp,cut:array[..]of int64;
f:array[..,..]of longint;
n,i,x,y,z,tot,time,que:longint; procedure add(a,b,c:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
len[tot]:=c;
head[a]:=tot;
end; function min(x,y:int64):int64;
begin
if x<y then exit(x);
exit(y);
end; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; function lca(x,y:longint):longint;
var i,d:longint;
begin
if dep[x]<dep[y] then swap(x,y);
d:=dep[x]-dep[y];
for i:= to do
if d and (<<i)> then x:=f[x,i];
for i:= downto do
if f[x,i]<>f[y,i] then
begin
x:=f[x,i]; y:=f[y,i];
end;
if x=y then exit(x);
exit(f[x,]);
end; procedure dfs(u:longint);
var e,i,v:longint;
begin
for i:= to do
begin
if dep[u]<(<<i) then break;
f[u,i]:=f[f[u,i-],i-];
end;
inc(time); dfn[u]:=time;
flag[u]:=;
e:=head[u];
while e<> do
begin
v:=vet[e];
if flag[v]= then
begin
f[v,]:=u;
dep[v]:=dep[u]+;
cut[v]:=min(cut[u],len[e]);
dfs(v);
end;
e:=next[e];
end;
end; procedure qsort(l,r:longint);
var i,j,mid:longint;
begin
i:=l; j:=r; mid:=b[(l+r)>>];
repeat
while mid>b[i] do inc(i);
while mid<b[j] do dec(j);
if i<=j then
begin
swap(h[i],h[j]);
swap(b[i],b[j]);
inc(i); dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end; procedure add1(a,b:longint);
begin
if a=b then exit;
// writeln(a,' ',b);
inc(tot);
next1[tot]:=head1[a];
vet1[tot]:=b;
head1[a]:=tot;
end; procedure dfs2(u:longint);
var e,v:longint;
s:int64;
begin
e:=head1[u]; dp[u]:=cut[u];
s:=;
while e<> do
begin
v:=vet1[e];
dfs2(v);
s:=s+dp[v];
e:=next1[e];
end;
head1[u]:=;
if s= then dp[u]:=cut[u]
else dp[u]:=min(s,dp[u]);
end; procedure solve;
var m,i,top,now,p,q:longint;
begin
read(m); tot:=;
for i:= to m do begin read(h[i]); b[i]:=dfn[h[i]]; end;
qsort(,m);
q:=;
for i:= to m do
if lca(h[q],h[i])<>h[q] then begin inc(q); h[q]:=h[i]; end;
//for i:= to q do writeln(h[i]);
stk[]:=; top:=;
for i:= to q do
begin
now:=h[i]; p:=lca(now,stk[top]);
while true do
begin
if dep[p]>=dep[stk[top-]] then
begin
add1(p,stk[top]); dec(top);
if stk[top]<>p then begin inc(top); stk[top]:=p; end;
break;
end;
add1(stk[top-],stk[top]); dec(top);
end;
if stk[top]<>now then begin inc(top); stk[top]:=now; end;
end;
repeat
dec(top);
if top<= then break;
add1(stk[top],stk[top+]);
until top=;
dfs2();
writeln(dp[]);
end; begin
assign(input,'bzoj2286.in'); reset(input);
assign(output,'bzoj2286.out'); rewrite(output);
readln(n);
for i:= to n- do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
readln(que);
//fillchar(cut,sizeof(cut),$1f);
cut[]:=oo;
dfs();
for i:= to que do solve;
close(input);
close(output);
end.