GDKOI2024-J D1D 题解
https://www.luogu.com.cn/discuss/805289
被打回 @ 2024-04-11 15:05
拒绝原因
解法存在事实性错误（你的代码保证不了除了 1 之外的点边权 xor 和都是 0 吧）；审核管理员：swiftc，对审核结果有疑问请私信交流
退役了懒得更新，就说明一下事实性错误
原题是 P5227 [AHOI2013] 连通图 但是数据范围开大了
LCT 做法、线段树分治都不凑效了，只能随机化。
考虑一个巧妙的套路：我们给这张图精细赋权，使得若删掉一些异或值恰好等于
理想很丰满，现实很骨感：首先需要暴力枚举边集来判断连通性。不过待判定的边集比较小，暴力枚举是没问题的。
主要麻烦在于构造。我们需要构造一张图，满足这个性质。
首先，一个很显然的性质就是，这个图必须满足一个点的所有出边异或值必为
然后，我们发现，对于任意一个子图，如果恰好与外部的点不连通了，且子集中每个点出边异或和都是
证明：考虑子图内部边的关系，一条边会被异或两次。因此子集内部所有边的异或和均为
所以，子集所有出边的异或和均为
观察到这个限制依旧是“又紧又松”：限制紧在每个点刚好满足条件，松在这里的边权选择极为自由，我们甚至可以开到 ULL 值域。
发现这只是一个简略的“判定性问题”，而且连通性问题是有比较多的试错可能的。
于是考虑，钦定
因为不连通之后，即使
一个节点特例，想到了什么？我们想到了树形结构。
于是接下来就到了喜闻乐见的乱搞构造环节。
任意取这张图以
- 若是非树边，则随机赋一个
[1,2^{64}) 的值； - 若是树边，则需要赋一个值，使得这个点它所有出边异或和为
0 。
观察到
具体看代码：
bool v[N];LL z[M],a[N];
mt19937_64 rd(time(0));
V dfs(I x,I fa=0){v[x]=1;
for(I _i=hd[x],y;y=ey[_i];a[x]^=z[_i>>1],_i=nx[_i])if(y!=fa){
if(v[y]&&!z[_i>>1])z[_i>>1]=rd()+1;
else if(!v[y])dfs(y,x),z[_i>>1]=a[y];}}异或值恰好等于
答案是：不能。
诶？为啥这个乱搞做法能过？这不科学！
思考反例：假设只抽一条边权，这条边不是关键边，抽到恰好是
那么抽一堆不是关键边的边，抽到的异或和为
所以我们就用随机构造过了这个题。
#include<bits/stdc++.h>
#define fo(i,a,b) for(I i(a),_ed(b);i<=_ed;++i)
#define gch(k) for(;(k);CH=getchar())
using namespace std;using I=int;using LL=long long;using V=void;I FL,CH;LL in(){LL a=0;FL=1;gch(!isdigit(CH))FL=(CH=='-')?-1:1;gch(isdigit(CH))a=a*10+CH-'0';return a*FL;}
const I M=4e6+10,N=1e6+10;
I ec=1,n,m,ey[M],nx[M],hd[N],x[M],y[M],q,id[4];
V conn(I x,I y){ey[++ec]=y;nx[ec]=hd[x];hd[x]=ec;}
bool v[N];LL z[M],a[N];
mt19937_64 rd(time(0));
V dfs(I x,I fa=0){v[x]=1;
for(I _i=hd[x],y;y=ey[_i];a[x]^=z[_i>>1],_i=nx[_i])if(y!=fa){
if(v[y]&&!z[_i>>1])z[_i>>1]=rd()+1;
else if(!v[y])dfs(y,x),z[_i>>1]=a[y];}}
bool pd(I k){LL vi;
fo(s,1,(1<<k)-1){vi=0;
fo(i,0,k-1)if(s&(1<<i))vi^=z[id[i]];
if(vi==0)return 0;}
return 1;}
I main(){
n=in();m=in();
fo(i,1,m){x[i]=in();y[i]=in();conn(x[i],y[i]);conn(y[i],x[i]);}
dfs(1);q=in();
while(q--){I k=in();
fo(i,0,k-1)id[i]=in();
puts(pd(k)?"ymqOAO":"Bob");}
return 0;}后记：其实这几个数对应的权值，还可以插入线性基里面，若都能插入，则异或值不为
这样就不需要