P10778 BZOJ3569 DZY Loves Chinese II 题解

· · 题解

题目传送门

前置知识

线性基 | 异或哈希

解法

强制在线限制了 luogu P5227 [AHOI2013] 连通图 的线段树分治无法通过。

注意到对于原图的一张生成树中的树边，如果它与覆盖它的返祖边都断开了就会变得不连通。

不妨考虑异或哈希，对返祖边随机赋权，树边的权值为覆盖它的返祖边的权值的异或和。询问时通过线性基判断能否正确插入来得到是否同时出现。

值得一提的是异或哈希能通过的重要限制是 k \le 15，即每次删的边不会太多。但是随着 k 的增长，错误性会逐渐扩大，且当 k> O(\log V) 后一定存在不能插入的情况（已经插满了）使得判断错误。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
mt19937_64 rng(random_device{}());
struct node
{
    int nxt,to,id;
}e[1000010];
int head[500010],u[500010],v[500010],vis[500010],ins[500010],cnt=0;
ull w[500010];
void add(int u,int v,int id)
{
    cnt++;  e[cnt]=(node){head[u],v,id};  head[u]=cnt;
}
void dfs(int x,int fa)
{
    vis[x]=ins[x]=1;
    for(int i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].id!=fa)
        {
            if(vis[e[i].to]==0)  dfs(e[i].to,e[i].id);
            else  if(ins[e[i].to]==1)  w[e[i].id]=rng();
            w[fa]^=w[e[i].id];
        }
    }
    ins[x]=0;
}
struct Liner_Base
{
    ull d[70];
    void clear()
    {
        memset(d,0,sizeof(d));
    }
    int insert(ull x)
    {
        for(int i=63;i>=0;i--)
        {
            if((x>>i)&1)
            {
                if(d[i]==0)
                {
                    d[i]=x;
                    return 1;
                }
                x^=d[i];
            }
        }
        return 0;
    }
}L;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m,q,k,x,ans=0,flag,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        add(u[i],v[i],i);  add(v[i],u[i],i);
    }
    dfs(1,0);
    scanf("%d",&q);
    for(i=1;i<=q;i++)
    {
        scanf("%d",&k);  L.clear();
        flag=1;
        for(j=1;j<=k;j++)
        {
            scanf("%d",&x);  x^=ans;
            flag&=L.insert(w[x]);
        }
        ans+=flag;
        if(flag==0)  printf("Disconnected\n");
        else  printf("Connected\n");
    }
    return 0;
}