上一题的强制在线版。对图跑出一个dfs树，给非树边赋上随机权值，树边的权值为覆盖他的非树边权值的异或。这样如果某条树边和覆盖他的非树边都被割掉（即图不连通），他们的异或值就为0。每次对询问看有没有子集异或值为0即可，可以简单地用线性基搞定。
#include#include #include #include #include #include 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 500010int n,m,k,p[N],t=1,lastans=0;bool flag[N];unsigned long long v[M],f[N],base[64];struct data{ int to,nxt;}edge[M<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs(int k,int from){ flag[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { if (!flag[edge[i].to]) dfs(edge[i].to,k); else v[i>>1]=rand()+1,v[i>>1]*=rand()+1,v[i>>1]*=rand()+1,v[i>>1]*=rand()+1; }}void getvalue(int k){ flag[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (!flag[edge[i].to]) { getvalue(edge[i].to); v[i>>1]=f[edge[i].to]; f[k]^=f[edge[i].to]; }}int main(){ freopen("bzoj3569.in","r",stdin); freopen("bzoj3569.out","w",stdout); n=read(),m=read(); srand(20020509*(m/n)); for (int i=1;i<=m;i++) { int x=read(),y=read(); addedge(x,y),addedge(y,x); } dfs(1,1); for (int i=2;i<=m*2+1;i++) if (i&1) f[edge[i].to]^=v[i>>1],f[edge[i^1].to]^=v[i>>1]; memset(flag,0,sizeof(flag)); getvalue(1); k=read(); for (int i=1;i<=k;i++) { int s=read(); memset(base,0,sizeof(base)); bool flag=1; for (int j=1;j<=s;j++) { int x=read()^lastans; unsigned long long w=v[x]; for (int l=63;~l;l--) if (w&(1ll<