这道题我开始的思路是采用普通向量的方法，来维护异或和，将赋值语句存到map中判定，之后再处理分奇偶处理询问
但是我发现了这个算法是错误的，因为这样我无法通过父节点维护子节点的赋值操作，比如 0 1 2，之后再对0赋值，这样其实1的值也知道了。
为了应对这个问题，可以考虑附加一个超级根节点n，将这个值的d设为0，因为0异或任何数等于那个数，所以不会影响，这样就能完美解决了
#include <iostream> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cmath> #include <ctime> using namespace std; typedef long long ll; const int N=1e5+10; int p[N],d[N]; map<int,int> m1; map<int,int> m2; int find(int x){ if(p[x]!=x){ int t=p[x]; p[x]=find(p[x]); d[x]^=d[t]; } return p[x]; } int n; int join(int x,int y,int z){ int pa=find(x),pb=find(y); if(pa==pb){ if((d[x]^d[y])!=z) return 0; else return 1; } else if(pa==n){ p[pb]=pa; d[pb]=d[x]^d[y]^z; } else{ p[pa]=pb; d[pa]=d[x]^d[y]^z; } return 1; } int main(){ int i; int q; int cnt=1; int x,y,z; while(cin>>n>>q){ if(n==0&&q==0) break; for(i=0;i<=n;i++){ p[i]=i; d[i]=0; } bool error=false; int flag=0; printf("Case %d: ",cnt++); char u[100]; for(i=0;i<q;i++){ string s; cin>>s; if(s=="I"){ flag++; gets(u); if(error) continue; int idx=sscanf(u,"%d %d %d",&x,&y,&z); if(idx==2){ z=y,y=n; if(!join(x,y,z)){ error=true; printf("The first %d facts are conflicting. ",flag); } } else{ if(!join(x,y,z)){ error=true; printf("The first %d facts are conflicting. ",flag); } } } else{ int can=1; int ans=0; map<int,int> m2; int k; cin>>k; for(int j=0;j<k;j++){ int x; cin>>x; if(error) continue; int pa=find(x); m2[pa]++; ans^=d[x]; } auto it=m2.begin(); for(it=m2.begin();it!=m2.end();it++){ if(it->second%2){ if(it->first!=n){ can=0; break; } } } if(error) continue; else{ if(can) cout<<ans<<endl; else printf("I don't know. "); } } } cout<<endl; } }