#C240815C. magic
网址（Website）
题解（Solution）
初看这道题的时候感觉很难，但是仔细分析后便会发现规律。
由于出现了 $mex$ 操作，肯定不能暴力求解，要先静下心来找规律。
首先考虑最后的与和没有 $0$ 的情况，那么对于两个点 $x$ 和 $y$ ，这两个点上的路径一定存在一个二进制位 $k$ 满足经过的路径上的所有的点的二进制表示下的第 $k$ 位都为 $1$ ，考虑对每一个进制位建图。
容易发现，对于询问的两点 $x$ 和 $y$ ，如果在任意图上这两个点联通，那么一定存在一条路径能使从 $x$ 走到 $y$ 的 mex{w1,w1&w2,⋯,w1&w2&⋯&wk} 为 $0$ 。由此，我们顺着思路考虑当前 mex{w1,w1&w2,⋯,w1&w2&⋯&wk} 不为 $0$ 的情况。
性质1：对于 mex{w1,w1&w2,⋯,w1&w2&⋯&wk}!=0 ，如果在路径上出现了一条偶数边，那么集合后面加入的所有的元素一定不可能为 $1$ ，则此时 mex{w1,w1&w2,⋯,w1&w2&⋯&wk} 必为 $1$；
性质2：对于 mex{w1,w1&w2,⋯,w1&w2&⋯&wk}!=0 ，当路径上只有奇数边时，最后的集合所有数的 $2^0$ 的二进制位一定为 $1$ ，那么无论怎么 & ，集合中一定不可能出现 $2$ 。
由上述性质得，最终的 mex{w1,w1&w2,⋯,w1&w2&⋯&wk} 只有 $0,1,2$ 三种可能，分别考虑三种情况。
对于
mex{w1,w1&w2,⋯,w1&w2&⋯&wk}=0，我们可以直接在按进制位建的图中用并查集分别维护连通块，两点在某个图中可以到达当且仅当两点在同一个并查集中，可以直接在建边的时候维护，时间复杂度 $O(mloga)$ 。对于
mex{w1,w1&w2,⋯,w1&w2&⋯&wk}=1，此时保证集合中存在 $0$ ，由于路径可以重复走，因此对于某个起点，只要找到一条偶边权的边使得这个点到达这条偶边前的路径集合中不出现 $1$ 即可。枚举每一条偶边，从它的两个点出发，在第 $1\sim 30$ 位二进制的图中标记所有能通往的点，将它们的 $flag$ 标为 $true$ ，判断两点是否存在mex{w1,w1&w2,⋯,w1&w2&⋯&wk}=1的路径时，只需要判断起点的 $flag$ 为 $true$ 即可，时间复杂度 $O(nloga)$ 。剩下的所有情况
mex{w1,w1&w2,⋯,w1&w2&⋯&wk}都为 $2$ ，输出即可。
对于每次询问，直接 $O(1)$ 输出即可，时间复杂度 $O(q)$ 。
总时间复杂度 $O(nloga+mloga)$ 。
代码（Code）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 201234;
const int K = 32;
bool ST;
int n,m,q;
int fa[N][K];
inline int find(int x,int k){
if(fa[x][k]==x) return x;
return fa[x][k] = find(fa[x][k],k);
}
bitset<N> flg[K],abl;
inline int solve(int x,int y){
For(k,0,30) if(find(x,k)==find(y,k)) return 0;
if(abl[x]) return 1;
else return 2;
}
bool ED;
//看到题目就开走，不跑样例是小狗
//不打暴力是小狗
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
cin>>n>>m;int Tim = clock();
For(k,0,30) For(i,1,n) fa[i][k] = i;
For(i,1,m){
int x,y,w,k=0;cin>>x>>y>>w;
if(w%2==0) abl[x] = abl[y] = true;
while(w){
if(w&1) fa[find(x,k)][k] = find(y,k);
w>>=1,k++;
}
}
For(x,1,n) if(abl[x]) For(k,1,30) flg[k][find(x,k)] = true;
For(x,1,n) For(k,1,30) abl[x] = abl[x] | flg[k][find(x,k)];
cin>>q;
while(q--){
int x,y;cin>>x>>y;
cout<<solve(x,y)<<'\n';
}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
