Problem - E - Codeforces
题意：
给定一个无向带权图，总共有 nn 个点 mm 条边，选定一个起点 uu 和终点 vv，现在你需要确定一条路径，设路径上的 kk 条边的边权为 w_1,w_2,\dots,w_kw1?,w2?,…,wk?，求出 MEX({w_1,w_1 & w_2,w_1&w_2&w_3,w_1&w_2&w_k}的最小值。其中 MEX 指集合中最小的不存在的自然数。
数据范围：n,m\le 10^5n,m≤105，边权 2^30。
题解：
答案为 00 的时候很简单，我们只需要判断是否从 u 到 v 存在一条路径，使得这条路径上的所有边权在二进制下某一位都为 1。只需要每一位建立一个并查集就可以了。
然后就是答案为 1 的情况了。
不难发现答案为 1 的时候，一定存在一个 r 使得 并且
。
换句话说，只要在走这一条边之前的与和大于 1，走之后与和为 0 就可以了，然后接下来怎么走都可以，所以这样答案与终点无关。
那么怎么得到这样一条路径呢？
显然我们需要选定一位i（不能是二进制下最低的一位！），然后从出发点走遍所有边权二进制这一位为 1 的边，然后我们只需要找是否存在一条边能够让与和变成 0。
具体用代码实现的话需要利用前面建立的并查集，并且记录每一个点所有的出边的边权的与和 fi?，然后算出在同一个联通块里面的点 fi? 的与和，如果是 0 代表这一个联通块内的点作为出发点可以做到答案为 1。
如果答案不是 0 也不是 1，那么答案就是 2 了。
/*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define MAX 0x3f3f3f3f
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=2e3+10;
const int mod=998244353;
int n,m,u,v,w,T,fa[30][maxn],f[maxn],s[maxn],flag[maxn];
int find(int x,int y){ if(fa[x][y]==y) return y; else return fa[x][y]=find(x,fa[x][y]);
}
int check0(){ for(int i=0;i<30;i++) if(find(i,u)==find(i,v)) return 1; return 0;
}
signed main(){cin>>n>>m;for(int i=0;i<30;i++) for(int j=1;j<=n;j++) fa[i][j]=j;for(int i=1;i<=n;i++) f[i]=(1<<30)-1;for(int i=1;i<=m;i++){cin>>u>>v>>w; f[u]&=w; f[v]&=w;for(int j=0;j<30;j++) if(w&(1<<j)) fa[j][find(j,u)]=find(j,v);}for(int k=1;k<30;k++){for(int i=1;i<=n;i++) s[i]=(1<<30)-1;for(int i=1;i<=n;i++) s[find(k,i)]&=f[i];for(int i=1;i<=n;i++) if(s[find(k,i)]==0) flag[i]=1;} cin>>T; while(T--){cin>>u>>v;if(check0()) puts("0"); else if(flag[u]) puts("1"); else puts("2");}
}