AcWing食物链
Q1：怎么判断X和Y是不是同类?
A:判断这俩是不是在一个集合中,如果在同一个集合中，那么判断X到祖先节点的距离D[X]和D[Y]到祖先节点的距离是否有D[X]%3=D[Y]%3,也就是3同余，这里D[X]%3=D[Y]%3是不可以直接在代码里面这样写的，d[X]和d[Y]有可能是负数，这样求出来的就WA了！只能按照标准答案里面那样写！
若果是，那么是同类。如果X和Y不在一个集合里面，那么把X和Y合并到一个集合里面。修改p[x]和d[px]
接着问题来了，如何正确修改p[x]和d[px]？
Q2:怎么判断X吃Y？
A:判断这俩是不是在一个集合中,如果在同一个集合中，那么判断
( d [ X ] + 1 ) % 3 = d [ Y ] % 3 (d[X]+1)\%3=d[Y]\%3 (d[X]+1)%3=d[Y]%3,如果是，那么X吃Y，若X和Y不在一个集合中那么合并X和Y，修改p[px],d[px]
#include<iostream>
#include<string>
#define LEN 100086
using namespace std;
int N,K,p[LEN],d[LEN];
int find(int x){if(p[x]!=x){int t=find(p[x]);d[x]+=d[p[x]];p[x]=t;}return p[x];
}
int main(){cin>>N>>K;int res=0;//假话个数for(int i=1;i<=N;++i){p[i]=i;}while(K--){int D,X,Y;cin>>D>>X>>Y;if(X>N||Y>N) {++res;continue;}if(D==2&&X==Y) {++res;continue;}int px=find(X),py=find(Y);if(D==1){if(px==py&&(d[X]-d[Y])%3){res++;}else if(px!=py){p[px]=py;d[px]=d[Y]-d[X];}}else if(D==2){if(px==py&&(d[X]-d[Y]-1)%3){res++;}else if(px!=py){p[px]=py;d[px]=d[Y]+1-d[X];}}}cout<<res<<endl;return 0;
}