题意很简单，有两个操作,一个是I p q v告诉你 x[p]^x[q]=v,一个是查询k个数的异或和，问是否出现矛盾以及能否确定答案
很经典的并查集问题
首先我们可以虚拟一个根节点x[n]=0，这样所有的I p v都可以转换成 x[p]^x[n]=0.另w[a]=x[a]^x[f[a]]即本身和父节点的异或值, 那么如何合并呢？记fp=f[p],fq=f[q],x[p]^x[q]=v,另f[fp]=fq的话，w[fp]=x[fp]^x[fq]=(x[p]^x[fp])^(x[p]^x[q])^(x[q]^x[fq])=w[p]^v^w[q],由此合并。难点在查询。x[a1]^x[a2]^...^x[ak]=w[a1]^w[a2]^..^w[ak]^x[f[a1]]^x [f[a2]]^...^x[f[ak]],前一部分直接求即可，后一部分只需求父节点出现次数为奇数次的，异或起来即可
github代码
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N=20005;
int ca,ca2,p,q,v,k,x,n,Q,f[N],w[N];
char s1[20],s2[20];
bool know,bug;
int find(int x){
if(f[x]!=x){
int fx=find(f[x]);
w[x]^=w[f[x]];
f[x]=fx;
}
return f[x];
}
void Union(int x,int y,int v){
int fx=find(x);
int fy=find(y);
if(fx==fy){
if((w[x]^w[y])!=v) bug=true;
return;
}
if(fx==n) swap(fx,fy);
f[fx]=fy;
w[fx]=w[x]^v^w[y]; //>_<
}
int main(){
while(scanf("%d%d",&n,&Q)&&n+Q){
++ca;
ca2=0;
bug=false;
for(int i=0;i<=n;++i) f[i]=i,w[i]=0;
printf("Case %d:\n",ca);
while(Q--){
scanf("%s",s1);
if(s1[0]==‘I‘){
++ca2;
gets(s1);
if(bug) continue;
int cnt=sscanf(s1,"%d%d%d",&p,&q,&v);
if(cnt==2) v=q,q=n;
Union(p,q,v);
if(bug) {printf("The first %d facts are conflicting.\n",ca2);continue;}
}
else{
know=true;
scanf("%d",&k);
int ans=0;
map<int,int>mp;
while(k--){
scanf("%d",&x);
int fx=find(x);
ans^=w[x];
mp[fx]++;
}
if(bug) continue;
map<int,int>::iterator it;
for(it=mp.begin();it!=mp.end();it++){
if(it->second%2){
if(it->first!=n) {know=false;break;}
else ans^=w[it->first];
}
}
if(!know) printf("I don‘t know.\n");
else printf("%d\n",ans);
}
}
printf("\n");
}
return 0;
}
Hdu 3234 & Uva 12232 Exclusive-OR
原文：http://blog.csdn.net/mlzmlz95/article/details/18815471