多维护一个和祖先节点的关系，由于路径压缩的原因，我们可以很方便的维护出这个关系 关键点：与根节点，路径压缩 下面是，一些数字，分为两类，判断是不是存不存在满足条件
int f[MX]; int tag[MX];//当前节点和根节点的关系,0表示相等.1表示不相等 vector<pair<pair<int,int>,int>>v; int find(int x) { if(x==f[x]) return x; else { int tmp=find(f[x]); tag[x]=(tag[x]+tag[f[x]])%2; return f[x]=tmp; } } void solve() { int n;cin>>n; v.clear(); vector<int>tmp; rpp(i,n) { int x,y,z;cin>>x>>y>>z; v.push_back(make_pair(make_pair(x,y),z)); tmp.push_back(x),tmp.push_back(y); } map<int,int>id; int cnt=0; for(auto x:tmp) { if(id[x]) continue; id[x]=++cnt; } n=cnt; rpp(i,n) f[i]=i,tag[i]=0; int flag = 1; for(auto op:v) { int x=id[op.first.first],y=id[op.first.second],z=!op.second; int fx=find(x),fy=find(y); if(fx==fy) { if((tag[x]^tag[y])==z) continue; else flag = 0; } else { tag[fy]=(z+tag[x]+tag[y])%2; f[fy] = fx; } cout<<endl<<endl; } if(flag) cout<<"YES\n"; else cout<<"NO\n"; }