消耗战（repair）
【问题描述】
在一场战争中，战场由n 个岛屿和n-1 个桥梁组成，保证每两个岛屿间有且
仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1 的岛屿，而且
他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k 个岛屿上有
丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能
到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥
梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们
也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会
重新随机资源分布（但可以保证的是，资源不会分布到1 号岛屿上）。不过侦查
部门还发现了这台机器只能够使用m 次，所以我们只需要把每次任务完成即可。
【输入格式】
第一行一个整数n，代表岛屿数量。
接下来n-1 行，每行三个整数u,v,w，代表u 号岛屿和v 号岛屿由一条代价为c
的桥梁直接相连，保证1<=u,v<=n 且1<=c<=100000。
第n+1 行，一个整数m，代表敌方机器能使用的次数。
接下来m 行，每行一个整数ki，代表第i 次后，有ki 个岛屿资源丰富，接下来k
个整数h1,h2,…hk，表示资源丰富岛屿的编号。
【输出格式】
输出有m 行，分别代表每次任务的最小代价。
【样例输入】
10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
32
10 6
4 5 7 8 3
3 9 4 6
【样例输出】
12
32
22
【数据规模和约定】
对于10%的数据，2<=n<=10,1<=m<=5,1<=ki<=n-1
对于20%的数据，2<=n<=100,1<=m<=100,1<=ki<=min(10,n-1)
对于40%的数据，2<=n<=1000,m>=1,sigma(ki)<=500000,1<=ki<=min(15,n-1)
对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
首先进行一遍dfs，对树进行扫描
扫描的时候得出每个点
到根节点路径上最小边权、
求lca所需的向上2的0、1、2……次方祖先
每个点的dfs序编号
每个点的高度
得出来之后，对于每次询问，将所有资源丰富的点按dfs序排序
相邻两个点dfs序靠近，说明他们在树中较为靠近
问题在于合并的顺序
这个使用一个单调栈来维护
从左到右扫描，假设扫描到i
那么比较height[lca(pre[pre[i]],pre[i])]和height[lca(pre[i],i)]
若前者小，那么i入栈
否则一直出栈合并两点直到小于为止
最后扫描完后，若栈内还有元素，则不断出栈合并
program repair;
var
high,x,y,t,u,v,w,tot,n,m,i,j,k,q,p:longint;
ans:int64;
xl,father,suc,pre,dl,height,num,root:array [0..250001] of longint;
up:array [0..21,0..250001] of longint;
cost:array [0..500001] of int64;
min,next,point:array [0..500001] of longint;
procedure connect (u,v,w:longint);
begin
inc(tot);
point[tot]:=v;
cost[tot]:=w;
next[tot]:=root[u];
root[u]:=tot;
end;
function lca (a,b:longint):longint;
var
k:longint;
begin
if height[a]>height[b] then
begin
k:=a;
a:=b;
b:=k;
end;
while height[a]<>height[b] do
begin
k:=trunc(ln(height[b]-height[a])/ln(2));
b:=up[k,b];
end;
if a=b then exit(a);
k:=trunc(ln(height[a]-1)/ln(2))+1;
repeat
while (k>0)and(up[k,a]=up[k,b]) do dec(k);
if up[k,a]=up[k,b] then exit(up[k,a]);
a:=up[k,a];
b:=up[k,b];
until false;
end;
procedure dfs;
var
i,k:longint;
begin
tot:=1;
num[1]:=1;
high:=1;
dl[1]:=1;
height[1]:=1;
min[1]:=maxlongint;
father[1]:=0;
while high>0 do
begin
i:=root[dl[high]];
if i=0 then
dec(high)
else
if point[i]<>father[dl[high]] then
begin
inc(tot);
num[point[i]]:=tot;
up[0,point[i]]:=dl[high];
k:=0;
while 1 shl (k+1)<=high do
begin
up[k+1,point[i]]:=up[k,up[k,point[i]]];
inc(k);
end;
up[k+1,point[i]]:=1;
root[dl[high]]:=next[i];
father[point[i]]:=dl[high];
if cost[i]<min[dl[high]] then min[point[i]]:=cost[i]
else min[point[i]]:=min[dl[high]];
inc(high);
dl[high]:=point[i];
height[point[i]]:=high;
end
else
root[dl[high]]:=next[i];
end;
end;
procedure qsort (s,e:longint);
var
i,j,k,o:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=num[dl[(s+e) div 2]];
while i<=j do
begin
while num[dl[i]]<k do inc(i);
while num[dl[j]]>k do dec(j);
if i>j then break;
o:=dl[i];
dl[i]:=dl[j];
dl[j]:=o;
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
begin
assign(input,'repair.in');
reset(input);
assign(output,'repair.out');
rewrite(output);
read(n);
for i:=1 to n-1 do
begin
read(u,v,w);
connect(u,v,w);
connect(v,u,w);
end;
tot:=0;
dfs;
point[0]:=0;
read(m);
for t:=1 to m do
begin
read(k);
for i:=1 to k do
read(dl[i]);
if k<20 then
for i:=1 to k-1 do
for j:=i+1 to k do
if num[dl[i]]<num[dl[j]] then
begin
x:=dl[i];
dl[i]:=dl[j];
dl[j]:=x;
end
else
else qsort(1,k);
suc[0]:=1;
pre[k+1]:=k;
for i:=1 to k do
begin
suc[i]:=i+1;
pre[i]:=i-1;
cost[i]:=min[dl[i]];
end;
tot:=0;
for i:=2 to k do
begin
while (tot>0)and
(height[lca(dl[i],dl[pre[i]])]<height[point[pre[i]]]) do
begin
x:=pre[i];
y:=point[x];
if (y<>1)and(min[y]<cost[x]+cost[pre[x]]) then
cost[x]:=min[y]
else
cost[x]:=cost[x]+cost[pre[x]];
dl[x]:=y;
suc[pre[pre[x]]]:=x;
pre[x]:=pre[pre[x]];
if pre[x]<>0 then point[x]:=lca(dl[x],dl[pre[x]]);
dec(tot);
end;
inc(tot);
point[i]:=lca(dl[i],dl[pre[i]]);
end;
x:=pre[k+1];
while tot>0 do
begin
y:=point[x];
if (y<>1)and(min[y]<cost[x]+cost[pre[x]]) then
cost[x]:=min[y]
else
cost[x]:=cost[x]+cost[pre[x]];
suc[pre[pre[x]]]:=x;
pre[x]:=pre[pre[x]];
dl[x]:=y;
if pre[x]<>0 then point[x]:=lca(dl[x],dl[pre[x]]);
dec(tot);
end;
writeln(cost[pre[k+1]]);
end;
close(input);
close(output);
end.