题解 P5227 【[AHOI2013]连通图】

· · 题解

神仙哈希题，复杂度 O(k\times \min(2^c,\log n)+n+m)，目前你谷最优解。

前置定义：非树边的覆盖树边指的是非树边的两个端点在树上的最短路覆盖的边。记 xor 为 \oplus。

考虑给非树边一个随机权值，而树边的权值为所有覆盖其的非树边的 \oplus，则删边不连通当且仅当删除的边集的一个子集 \oplus 是 0，这个可以在 c 小的时候枚举子集、c 大的时候线性基实现。树边的权值可以通过树上差分快速修改。

证明：考虑被分开的两个极大连通点集之间被删掉的边的 \oplus。考虑每条非树边产生的贡献。若这条边两端在同一点集（设为 A），那么其覆盖的被删除树边必定是 A\to B\to A \to B\to A，偶数次；若这条边两端在不同点集则出现奇数次，加上非树边本身还是偶数次，因而 \oplus 必定为 0。

当 \oplus 为 0 时，由于我比较懒，就只证 dfs 树的情况了。

显然这些边至少有一条树边，设深度最小的那条为 (fa_u,u)。考虑树边为 (fa_u,u)，那么若 fa_u 和 u 还能连通，必定是通过 u 子树出发的某条非树边 (x,y)（x 在 u 子树内） 跳到 fa_u 的祖先。由于 (fa_u,u) 深度最小，因此 fa_u 到 y 的路径上边都未断开。由于 (x,y) 没有贡献，那么要么自身被删了，要么 (x,u) 上还有另一条边被删了，无论哪种 u 都不能经过 (x,y) 到达深度更小的节点。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
const int N=1e5+2,M=2e5+2;
ll v[N],val[M],js;
int lj[M],nxt[M],bh[M],fir[N],f[N];
int n,m,i,x,y,z,c,bs;
inline void read(int &x)
{
    c=getchar();
    while ((c<48)||(c>57)) c=getchar();
    x=c^48;c=getchar();
    while ((c>=48)&&(c<=57))
    {
        x=x*10+(c^48);
        c=getchar();
    }
}
int getf(int x)
{
    if (f[x]==x) return x;
    return f[x]=getf(f[x]);
}
inline ll sj()
{
    js=rand();js<<=31;return js|rand();
}
inline void add(int x,int y,int z)
{
    lj[++bs]=y;
    bh[bs]=z;
    nxt[bs]=fir[x];
    fir[x]=bs;
    lj[++bs]=x;
    bh[bs]=z;
    nxt[bs]=fir[y];
    fir[y]=bs;
}
void dfs(int x)
{
    int i;
    for (i=fir[x];i;i=nxt[i]) if (lj[i]!=f[x])
    {
        f[lj[i]]=x;
        dfs(lj[i]);
        v[x]^=(val[bh[i]]=v[lj[i]]);
    }
}
int main()
{
    srand(383778817);
    read(n);read(m);
    for (i=1;i<=n;i++) f[i]=i;
    for (i=1;i<=m;i++)
    {
        read(x);read(y);
        if (getf(x)==getf(y)) {v[x]^=(val[i]=sj());v[y]^=val[i];}
        else {add(x,y,i);f[f[x]]=f[y];}
    }memset(f,0,sizeof(f));dfs(1);read(m);
    while (m--)
    {
        read(x);
        if (x==1) {read(y);if (val[y]) puts("Connected"); else puts("Disconnected");}
        else if (x==2) {read(y);read(z);if ((val[y])&&(val[y]^val[z])&&(val[z])) puts("Connected"); else puts("Disconnected");}
        else if (x==3) {read(y);read(z);read(i);if ((val[y])&&(val[z])&&(val[i])&&(val[y]^val[z])&&(val[z]^val[i])&&(val[y]^val[i])&&(val[y]^val[z]^val[i])) puts("Connected"); else puts("Disconnected");}
        else {read(x);read(y);read(z);read(i);if ((val[x])&&(val[y])&&(val[z])&&(val[i])&&(val[x]^val[y])&&(val[x]^val[z])&&(val[x]^val[i])&&(val[z]^val[y])&&(val[i]^val[y])&&(val[z]^val[i])&&(val[x]^val[y]^val[z])&&(val[x]^val[y]^val[i])&&(val[x]^val[i]^val[z])&&(val[i]^val[y]^val[z])&&(val[x]^val[y]^val[z]^val[i])) puts("Connected"); else puts("Disconnected");}
    }
}