首页 > 代码库 > bzoj2286 [Sdoi2011]消耗战

bzoj2286 [Sdoi2011]消耗战

Description

在一场战争中,战场由n个岛屿和n-1个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为1的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他k个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。
侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到1号岛屿上)。不过侦查部门还发现了这台机器只能够使用m次,所以我们只需要把每次任务完成即可。

Input

第一行一个整数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,表示资源丰富岛屿的编号。

 

Output

输出有m行,分别代表每次任务的最小代价。

 

Sample Input

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
3
2 10 6
4 5 7 8 3
3 9 4 6

Sample Output

12
32
22
 

HINT

 对于100%的数据,2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

 

Source

Stage2 day2

 

 

这个应该是虚树的入门题吧

  1 program repair(input,output);
  2 const
  3   inf=123456789;
  4 type
  5   etype=record
  6      t,next:longint;
  7      w:int64;
  8   end;
  9 var
 10   b,e:array[0..500050]of etype;
 11   father:array[0..500050,0..20]of longint;
 12   v:array[0..250025]of boolean;
 13   a,d,head,q,dfn,fa:array[0..250025]of longint;
 14   w,f:array[0..250025]of int64;
 15   c:array[0..500050]of longint;
 16   n,m,i,j,k,x,y,cnt,top,h,t,r:longint;
 17   z:int64;
 18 procedure add(x,y:longint;w:int64);
 19 begin
 20    inc(cnt);e[cnt].t:=y;e[cnt].w:=w;e[cnt].next:=a[x];a[x]:=cnt;
 21 end;
 22 function min(a,b:int64):int64;
 23 begin
 24    if a<b then exit(a) else exit(b);
 25 end;
 26 procedure dfs(k:longint);
 27 var
 28   i:longint;
 29 begin
 30    inc(cnt);dfn[k]:=cnt;if d[k]>r then r:=d[k];
 31    i:=a[k];
 32    while i<>0 do
 33       begin
 34          if dfn[e[i].t]=0 then
 35             begin
 36                father[e[i].t,0]:=k;d[e[i].t]:=d[k]+1;w[e[i].t]:=min(w[k],e[i].w);
 37                dfs(e[i].t);
 38             end;
 39          i:=e[i].next;
 40       end;
 41 end;
 42 procedure sort(q,h:longint);
 43 var
 44   i,j,x,t:longint;
 45 begin
 46    i:=q;j:=h;x:=dfn[c[(i+j)>>1]];
 47    repeat
 48      while dfn[c[i]]<x do inc(i);
 49      while x<dfn[c[j]] do dec(j);
 50      if i<=j then
 51         begin
 52            t:=c[i];c[i]:=c[j];c[j]:=t;
 53            inc(i);dec(j);
 54         end;
 55    until i>j;
 56    if j>q then sort(q,j);
 57    if i<h then sort(i,h);
 58 end;
 59 function lca(x,y:longint):longint;
 60 var
 61   t:longint;
 62 begin
 63    if d[x]<d[y] then begin t:=x;x:=y;y:=t; end;
 64    for k:=r downto 0 do if d[father[x,k]]>=d[y] then x:=father[x,k];
 65    if x=y then exit(x);
 66    for k:=r downto 0 do if father[x,k]<>father[y,k] then begin x:=father[x,k];y:=father[y,k]; end;
 67    exit(father[x,0]);
 68 end;
 69 procedure ins(x,y:longint);
 70 begin
 71    inc(cnt);b[cnt].t:=y;b[cnt].next:=head[x];head[x]:=cnt;
 72 end;
 73 begin
 74    assign(input,repair.in);assign(output,repair.out);reset(input);rewrite(output);
 75    readln(n);cnt:=0;
 76    fillchar(a,sizeof(a),0);
 77    for i:=2 to n do begin read(x,y,z); add(x,y,z);add(y,x,z); end;
 78    fillchar(dfn,sizeof(dfn),0);cnt:=0;father[1,0]:=0;d[1]:=1;
 79    for i:=1 to n do w[i]:=inf;r:=0;
 80    dfs(1);
 81    k:=0;i:=1;
 82    while i<r do begin i:=i+i;inc(k); end;
 83    r:=k;
 84    for j:=1 to r do for i:=1 to n do father[i,j]:=father[father[i,j-1],j-1];
 85    readln(m);
 86    fillchar(head,sizeof(head),0);fillchar(v,sizeof(v),false);fillchar(f,sizeof(f),0);
 87    for i:=1 to m do
 88       begin
 89          read(x);for j:=1 to x do begin read(c[j]);v[c[j]]:=true; end;
 90          sort(1,x);y:=x;
 91          for j:=2 to x do begin inc(y);c[y]:=lca(c[j],c[j-1]);if c[y]=1 then dec(y); end;
 92          sort(1,y);x:=1;
 93          for j:=2 to y do if c[j]<>c[j-1] then begin inc(x);c[x]:=c[j]; end;
 94          top:=1;q[1]:=1;cnt:=0;
 95          for j:=1 to x do
 96             begin
 97                while lca(q[top],c[j])<>q[top] do dec(top);
 98                fa[c[j]]:=q[top];ins(q[top],c[j]);
 99                inc(top);q[top]:=c[j];
100             end;
101          h:=0;t:=1;q[1]:=1;
102          while h<t do
103             begin
104                inc(h);
105                j:=head[q[h]];
106                while j<>0 do begin inc(t);q[t]:=b[j].t;j:=b[j].next; end;
107             end;
108          for j:=x+1 downto 2 do
109             begin
110                if (w[q[j]]<f[q[j]]) or v[q[j]] then f[q[j]]:=w[q[j]];
111                inc(f[fa[q[j]]],f[q[j]]);
112             end;
113          writeln(f[1]);
114      for j:=1 to x do begin v[c[j]]:=false;f[c[j]]:=0;head[c[j]]:=0; end;f[1]:=0;head[1]:=0;
115       end;
116    close(input);close(output);
117 end.

 

bzoj2286 [Sdoi2011]消耗战