把查询看做是在一条时间轴上。那么每条边都有几段存在时间。于是线段树分治就好了。
然而在bzoj上t掉了，不知道是常数大了还是写挂了。
以及brk不知道是啥做数组名过不了编译。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> #include<stack> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 100010 #define M 200010 int n,m,k,L[N<<2],R[N<<2],fa[N],size[N]; bool ans[N]; struct edge{int x,y;}e[M]; vector<edge> tree[N<<2]; vector<int> bre[M]; stack<edge> undo[N<<2]; void build(int k,int l,int r) { L[k]=l,R[k]=r; if (l==r) return; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } void add(int k,int l,int r,edge e) { if (L[k]==l&&R[k]==r) {tree[k].push_back(e);return;} int mid=L[k]+R[k]>>1; if (r<=mid) add(k<<1,l,r,e); else if (l>mid) add(k<<1|1,l,r,e); else add(k<<1,l,mid,e),add(k<<1|1,mid+1,r,e); } int find(int x){return fa[x]==x?x:find(fa[x]);} void merge(int k,int x,int y) { if (size[x]<size[y]) swap(x,y); edge a;a.x=x,a.y=y; undo[k].push(a); fa[y]=x;size[x]+=size[y]; } void solve(int k) { int s=tree[k].size(); for (int i=0;i<s;i++) { int p=find(tree[k][i].x),q=find(tree[k][i].y); if (p!=q) merge(k,p,q); } if (size[find(1)]==n) for (int i=L[k];i<=R[k];i++) ans[i]=1; else if (L[k]<R[k]) solve(k<<1),solve(k<<1|1); while (!undo[k].empty()) { edge a=undo[k].top(); fa[a.y]=a.y;size[a.x]-=size[a.y]; undo[k].pop(); } } int main() { n=read(),m=read(); for (int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(); k=read(); for (int i=1;i<=k;i++) { int s=read(); for (int j=1;j<=s;j++) { int x=read(); bre[x].push_back(i); } } build(1,1,k); for (int i=1;i<=m;i++) { int s=bre[i].size(); if (s==0) add(1,1,k,e[i]); else { if (bre[i][0]-1>=1) add(1,1,bre[i][0]-1,e[i]); for (int j=1;j<s;j++) if (bre[i][j]-1>=bre[i][j-1]+1) add(1,bre[i][j-1]+1,bre[i][j]-1,e[i]); if (bre[i][s-1]+1<=k) add(1,bre[i][s-1]+1,k,e[i]); } } for (int i=1;i<=n;i++) fa[i]=i,size[i]=1; solve(1); for (int i=1;i<=k;i++) if (ans[i]) printf("Connected "); else printf("Disconnected "); return 0; }