bzoj3237

首先我们可以把没有询问过的边处理掉，重构图

当然这样也不影响复杂度

考虑到每次询问要删除的边很少，我们完全可以整体处理

把询问划分成两个集合，在前半部分询问未出现边我们可以整体处理掉，缩点重编号（询问的边和点都要重编号）

然后通过分治继续对前半部分做

然后回来，后半部分我们也可以同样的处理

这样我们要维护一个关于当前边集的栈即可

UPD：省队集训的时候听到一种非常神的的随机化做法，摘录如下：

Step1：随便建立一颗生成树；

Step2：对于每一条不在生成树上的边，随机一个64位整数作为这条边的权值；

Step3：对于每条在生成树上的边，定义它的权值为连接他的两个端点对应部分的所有非树边的权值的xor和；

Step4：对于每一组询问，枚举询问中边的子集，如果某个子集所对应的边的权值xor和等于0，则我们可以断言，去掉这些边以后图不连通；否则，去掉这些边不影响图的连通性。

证明我有时间在放上来吧（并不会……），不过很明显这个复杂度随便操cdq分治

  1 type node=record
  2        x,y:longint;
  3      end;
  4 var e:array[0..200010] of node;
  5     te:array[0..4000010] of node;
  6     q:array[0..100010,0..4] of longint;
  7     h,fa:array[0..100010] of longint;
  8     v,ans:array[0..200010] of boolean;
  9     mh:array[0..200010] of longint;
 10     t,tm,th,n,m,k,i,j:longint;
 11 
 12 function getf(x:longint):longint;
 13   begin
 14     if fa[x]<>x then fa[x]:=getf(fa[x]);
 15     exit(fa[x]);
 16   end;
 17 
 18 procedure lab(n,m,l,r:longint);
 19   var i,j,x,y:longint;
 20   begin
 21     for i:=1 to n do
 22       fa[i]:=i;
 23     for i:=1 to m do
 24       if not v[i] then
 25       begin
 26         x:=getf(e[i].x); y:=getf(e[i].y);
 27         if x<>y then fa[x]:=y;
 28       end;
 29     th:=0;
 30     for i:=1 to n do
 31       if fa[i]=i then
 32       begin
 33         inc(th);
 34         h[i]:=th;
 35       end;
 36     for i:=1 to n do
 37       h[i]:=h[getf(i)];
 38     tm:=0;
 39     for i:=1 to m do
 40       if v[i] then
 41       begin
 42         inc(tm);
 43         mh[i]:=tm;
 44         e[tm].x:=h[e[i].x];
 45         e[tm].y:=h[e[i].y];
 46       end;
 47     for i:=l to r do
 48       for j:=1 to q[i,0] do
 49         q[i,j]:=mh[q[i,j]];
 50   end;
 51 
 52 procedure mark(l,r:longint);
 53   var i,j:longint;
 54   begin
 55     for i:=l to r do
 56       for j:=1 to q[i,0] do
 57         v[q[i,j]]:=true;
 58   end;
 59 
 60 procedure cdq(n,m,l,r:longint);
 61   var mid,i:longint;
 62   begin
 63     if l=r then
 64     begin
 65       ans[l]:=true;
 66       for i:=1 to q[l,0] do
 67         if e[q[l,i]].x<>e[q[l,i]].y then
 68         begin
 69           ans[l]:=false;
 70           break;
 71         end;
 72       exit;
 73     end;
 74     mid:=(l+r) shr 1;
 75     for i:=1 to m do
 76     begin
 77       inc(t);
 78       te[t]:=e[i];  //te维护边的栈
 79       v[i]:=false;
 80     end;
 81     mark(l,mid);
 82     lab(n,m,l,mid);
 83     cdq(th,tm,l,mid);
 84     for i:=m downto 1 do
 85     begin
 86       e[i]:=te[t];
 87       dec(t);
 88       v[i]:=false;
 89     end;
 90     mark(mid+1,r);
 91     lab(n,m,mid+1,r);
 92     cdq(th,tm,mid+1,r);
 93   end;
 94 
 95 begin
 96   readln(n,m);
 97   for i:=1 to m do
 98     readln(e[i].x,e[i].y);
 99   readln(k);
100   for i:=1 to k do
101   begin
102     read(q[i,0]);
103     for j:=1 to q[i,0] do
104       read(q[i,j]);
105     readln;
106   end;
107   mark(1,k);
108   lab(n,m,1,k);
109   cdq(th,tm,1,k);
110   for i:=1 to k do
111     if ans[i] then writeln('Connected')
112     else writeln('Disconnected');
113 end.

View Code