自动搬运

查看原文

来自洛谷，原作者为

	CYZZ 能卷是一种幸运

搬运于2025-08-24 23:01:08，当前版本为作者最后更新于2024-07-14 10:36:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 跑生成树。

• 对于非树边，边权随机
• 对于树边，边权为儿子节点已确定的出边的边权异或和（这样 xor 起来为零）。

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，放最后是因为怕有人跑了。