很明显，20%=mincut 40%=每次暴力树形dp

那么正解是什么呢？不难发现∑ki<=500000,也就是每次询问的复杂度都要跟k有关

从树形dp工作的角度来看，确实有很多点我们根本就没必要访问，我们设每次要割断的岛屿为关键点

这里引入了一个新的东西叫做虚树，简单来说就是把树上没用的点去掉收缩成一棵树

具体来说，如果一个点的子树中至多只有一棵子树包含关键点，那么这个点就可以删掉

也就是说只有关键点和他们的lca会被保留下来就行了，证明总点数<=2*k-1

那么怎么构建虚树？我们先按dfs序排序，然后按这个顺序不断加点维护虚树上最新的路径

感觉建树的方法只可意会不可言传，具体见代码吧……

1 type node=record  2        len,po,next:longint;  3      end;  4   5 var e:array[0..500010] of node;  6     anc:array[0..250010,0..20] of longint;  7     b,d,p,c,fa,st,a:array[0..250010] of longint;  8     f:array[0..250010] of int64;  9     v:array[0..250010] of boolean; 10     w,s,m,h,t,n,len,i,x,y,z:longint; 11  12 function min(a,b:longint):longint; 13   begin 14     if a>b then exit(b) else exit(a); 15   end; 16  17 procedure swap(var a,b:longint); 18   var c:longint; 19   begin 20     c:=a; 21     a:=b; 22     b:=c; 23   end; 24  25 procedure sort(l,r: longint); 26   var i,j,x:longint; 27   begin 28     i:=l; 29     j:=r; 30     x:=b[a[(l+r) shr 1]]; 31     repeat 32       while b[a[i]]
      
       j) then 35       begin 36         swap(a[i],a[j]); 37         inc(i); 38         j:=j-1; 39       end; 40     until i>j; 41     if l
       
        0 then anc[x,i]:=anc[y,i-1] 63       else break; 64     end; 65     i:=p[x]; 66     while i<>0 do 67     begin 68       y:=e[i].po; 69       if fa[x]<>y then 70       begin 71         fa[y]:=x; 72         anc[y,0]:=x; 73         c[y]:=min(c[x],e[i].len);  //c[]表示把这个点和根节点割开最小代价 74         d[y]:=d[x]+1; 75         dfs(y); 76       end; 77       i:=e[i].next; 78     end; 79   end; 80  81 function lca(x,y:longint):longint; 82   var i,p:longint; 83   begin 84     if d[x]
        
         d[y] then 87       for i:=p downto 0 do 88         if d[x]-1 shl i>=d[y] then x:=anc[x,i]; 89     if x=y then exit(x); 90     for i:=p downto 0 do 91       if (anc[y,i]<>anc[x,i]) then 92       begin 93         x:=anc[x,i]; 94         y:=anc[y,i]; 95       end; 96     exit(fa[x]); 97   end; 98  99 procedure dp(x:longint);  //dp过程很简单100   var i,y:longint;101       s:int64;102   begin103     if x=1 then f[1]:=2147483647*2147483647104     else f[x]:=c[x];105     i:=p[x];106     s:=0;107     while i<>0 do108     begin109       y:=e[i].po;110       dp(y);111       s:=s+f[y];112       i:=e[i].next;113     end;114     p[x]:=0;115     if (s<>0) then116       if f[x]>s then f[x]:=s;117   end;118 119 begin120   readln(n);121   h:=trunc(ln(n)/ln(2));122   for i:=1 to n-1 do123   begin124     readln(x,y,z);125     add(x,y,z);126     add(y,x,z);127   end;128   c[1]:=2147483647;129   dfs(1);130   readln(m);131   fillchar(p,sizeof(p),0);132   while m>0 do133   begin134     dec(m);135     read(s);136     for i:=1 to s do137       read(a[i]);138 139     sort(1,s);140     w:=1;141     for i:=2 to s do142       if lca(a[w],a[i])<>a[w] then  //这里一点点优化，如果存在祖先关系的关键点，肯定割祖先以上的边143       begin144         inc(w);145         a[w]:=a[i];146       end;147     len:=0;148     st[1]:=1;149     t:=1;150     for i:=1 to w do151     begin152       x:=a[i];153       z:=lca(x,st[t]); 154       while d[z]
         
          =d[st[t-1]] then157         begin158           add(z,st[t],0);159           dec(t);160           if st[t]<>z then161           begin162             inc(t);163             st[t]:=z;164           end;165           break;166         end;167         add(st[t-1],st[t],0);  //把原来分叉的那段建出来168         dec(t);169       end;170       if st[t]<>x then171       begin172         inc(t);173         st[t]:=x;174       end;175     end;176     while t>1 do   //把维护的路径建出来177     begin178       add(st[t-1],st[t],0);179       dec(t);180     end;181     dp(1);182     writeln(f[1]);183   end;184 end.