一道不是那么传统的带权并查集
题目特殊的地方在于运算是异或，不是像经典的带权并查集那样可以有一个恒定的子节点与父结点的递推关系。比如传统的求一个结点到根结点的距离的并查集可以这样写
int findfat(int x)
{
if(fat[x] == x) return x;
int tmp=fat[x];
fat[x]=findfat(fat[x]);
//在此处修改val比如：
value[x]=value[tmp]+1;
return fat[x];
}
这样写的正确性在于这个递推关系一定是正确的，即使在森林里改变任意一个点的数值，在他的后代执行findfat的时候也一定能更新所有的数值。但是异或是不太一样的，如果直接写 value[x]=value[x]^value[tmp]，的话，仅仅是对x求两次查找根结点而不做任何其他操作就会使得数值出现错误，因为w[x]等于和自己又异或了一次，就会出现不正常的结果。
思考了一下，我直接把w数组定义为：w[i]表示i点当前的真实值，这和之前的那种并查集的权是不太一样，经典的算法一般是定义这个东西为一个从根结点到当前结点的一个累积的东西。，而在我这里这个异或值其实某种程度上也可以认为是那种定义，只要把根结点都设为0就行了。
但是这样的话会有新的问题，没有一个稳定的递推关系那该如何保证所有的数值在取到它的时候是正确的，如果每次都更新还是会还出现之前说的重复异或的问题。我这里用了一个比较屌丝的方法，新增了一个辅助数值pp[i]表示 “从i向根结点看i结点以为的他的直接父结点的w值” ，这样的话，只要在并查集搜索递归之后的判断这个pp值是否发生了变化就知道当前的结点需不需要更新了。
然后就是类似于经典的并查集，合并之类的操作，用子结点确知值更新root之类的，这些都比较简单。
最后说下坑点，这个最后判断是否为I don’t know. 的时候，我一开始直接判断当有不同的root且没有这个root确定下来数值的时候就判断为不知道，由此wa了很久。。。后来才意识到如果一棵树里取到了偶数个结点的话即使是root不确定，他们的异或值也是确定的，因为root被异或了偶数次等于0了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 4e4 + 5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int p[maxn],w[maxn],pp[maxn];
bool cs[maxn];
char tmp[1000],vis[1000006];
vector<int> vec;
int fd(int x){
if(x==p[x]){
return x;
}
else {
int t=p[x],d=w[p[x]];
p[x]=fd(p[x]);
if(pp[x]!=w[t])
w[x]=((w[x])^w[t]),pp[x]=w[p[x]];
cs[x]=cs[p[x]];
return p[x];
}
}
int main()
{
int n,q,u,v,a,pa,flag,k,cas=0,fcs=0;
char op;
while(~scanf("%d%d",&n,&q)&&n){
cas++;
printf("Case %d:\n",cas);
memset(cs,0,sizeof(cs));
memset(w,0,sizeof(w));
for(int i=1;i<=n;i++){
p[i]=i,pp[i]=0;
}
flag=1;fcs=0;
for(int i=1;i<=q;i++){
scanf(" %c",&op);
if(op=='I'){
fcs++;
fgets(tmp,100,stdin);
op=sscanf(tmp,"%d%d%d",&u,&v,&a);
if(op==2){
if(!flag) continue;
u++;
pa=fd(u);
if(cs[pa]){
if(v!=w[u])
printf("The first %d facts are conflicting.\n",fcs),flag=0;
}
else{
w[pa]=(w[u]^v);
cs[pa]=1;
}
}
else{
u++,v++;
if(u==v){
if(a!=0)
printf("The first %d facts are conflicting.\n",fcs),flag=0;
}
if(!flag) continue;
int p1=fd(u),p2=fd(v);
if(p1!=p2){
if(cs[u]&&cs[v]){
if((w[u]^w[v])!=a)
printf("The first %d facts are conflicting.\n",fcs),flag=0;
}
else{
if(cs[p1]==0)
swap(p1,p2),swap(u,v);
p[p2]=p1;
pp[p2]=w[p1];
w[p2]=(((w[u]^a)^w[v]));
}
}
else{
if((w[u]^a)!=w[v])
printf("The first %d facts are conflicting.\n",fcs),flag=0;
}
}
}
else{
scanf("%d",&k);
int pre,cur,ans=0;
if(!flag){
for(int i=1;i<=k;i++)
scanf("%d",&ans);
continue;
}
vec.clear();
bool fuck=1;
int p2;
for(int i=1;i<=k;i++){
scanf("%d",&cur);cur++;
if(!flag) continue;
p2=fd(cur);
vec.push_back(p2);
vis[p2]++;
ans^=w[cur];
}
for(int i=0;i<vec.size();i++){
if(cs[vec[i]]==0&&vis[vec[i]]%2) fuck=0;
vis[vec[i]]=0;
}
if(fuck==0)
puts("I don't know.");
else if(flag)
printf("%d\n",ans);
}
}
puts("");
}
return 0;
}