P10778 题解

· · 题解

DZY Loves Chinese II

Part 0

省流：从 chen_zhe 犇犇跑过来的。

声明：本题解是正向推导，所以相较于直接给构造方式来说会比较冗长，但是有助于理解。

Part 1

首先，可以线段树分治，但是不但不能在线，而且复杂度太高。所以，我们需要找到一个非数据结构的快速处理询问的方法。

思考什么时候图会不连通，不妨设图被分为了两个连通块 S,V-S（其余情况一定能规约到这种），考虑如何快速判断 S 与 V-S 不连通。

寻找哪些边是一定要被割掉的，发现 E'_S=\{(u,v)\in E\mid u\in S,v\in V-S\} 这个边集一定要被割掉（即切断 S 与外界的联系）。

我们要想知道一个询问边集是否合法，就要知道是否存在一个 E' 是询问边集的子集。对于每个 S 都记录一个 E' 是不可能的，于是我们要方便地刻画这个 E'。

接下来有个很 wisdom 的想法，考虑随机异或哈希：假如我们给每条边赋一个权值 w，使得对于所有 E' 都满足 \bigoplus\limits_{e\in E'}w_e=0。

如果已能解决构造边权的部分（Part 2），剩下的就是：判断是否存在一个询问边集的子集，满足这个子集的边权异或和为 0。这个问题可以轻易地用线性基解决。

Part 2

问题变为：如何构造能够满足所有 E' 条件的权值。

先考虑最简单的情况：S 为一个点，此时 E' 为这个点的所有出边。也就是说，每个点的出边的权值异或和为 0（条件 1.）。

然而，我们发现满足这个条件就足够了，为什么呢？

如果 S 里只有两个点，设为 x,y，发现 E'_S=(E'_{\{x\}} \cup E'_{\{y\}})-(E'_{\{x\}} \cap E'_{\{y\}})。

换句话说，把两端都在 S 里的边去掉被抵消掉了，而 xor 和刚好就能体现“抵消”的性质。（这里可能比较抽象，建议自己手玩理解）。

而推广到三个点，四个点，n 个点都是一样的，同样可以由条件 1. 推出。

问题变为：如何满足条件 1.。

这个就比较简单了：随便 dfs 跑生成树。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define M 500005
#define V 65
#define ll unsigned long long
int n,m,q;
namespace GRAPH
{
    int tot=1,head[N];ll w[M];
    struct Edge{int next,to;}e[M<<1];
    void add_edge(int u,int v){e[++tot]={head[u],v};head[u]=tot;}
    int idx,dfn[N],bk[N];mt19937_64 seed(847532);
    void dfs(int u,int from)
    {
        dfn[u]=++idx;bk[u]=1;ll sum=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;if((i>>1)==from) continue;
            if(bk[v])
            {
                if(dfn[v]<dfn[u])
                    w[i>>1]=seed();
            }
            else dfs(v,i>>1);
            sum^=w[i>>1];
        }
        w[from]=sum;
    }
}using namespace GRAPH;
namespace Linear_Basis
{
    ll p[V];
    inline void Clear(){memset(p,0,sizeof p);}
    inline bool Insert(ll x)
    {
        for(int i=63;~i;i--) if(x>>i&1)
        {
            if(p[i]) x^=p[i];
            else return p[i]=x,1;
        }
        return 0;
    }
}using namespace Linear_Basis;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        add_edge(x,y);add_edge(y,x);
    }
    dfs(1,0);scanf("%d",&q);
    ll lst=0;
    while(q--)
    {
        int cnt,flag=1;scanf("%d",&cnt);
        for(int i=1;i<=cnt;i++)
        {
            int x;scanf("%d",&x);x^=lst;
            flag&=Insert(w[x]);
        }
        Clear();lst+=flag;
        printf("%s\n",flag?"Connected":"Disconnected");
    }
}

多倍经验：P5227，P10075，P10774，放最后是因为怕有人跑了。