三种动物种类，他们之间互吃：

之后k句话，有真有假，三个判别条件：

具体解释:

1.如果前面说了X吃Y，后面再说Y吃X，那么显然，Y吃X是假话。

2.如果一共只有100号动物，他说1000号动物怎么样，明显假话。

3.如果说X吃X，是假话。

本题采用并查集，但多了个距离维护，我们用节点到根节点的距离来算他们的关系。

例如我们让A为根节点，那么用d数组来表示，当前节点编号到根节点的距离（但在实际初始化中，d一开始表示的是到父节点的距离，但因为路径压缩优化，最终父节点都是根节点）。

d[0]=0,d[20]=1,d[24]=2,d[30]=0。

那么我们就可以知道，只要距离%3，为0就是与根节点同类，为1就是被根节点吃，为2就是吃根节点，我们也可以通过他们与根节点的关系，判断它们之间的关系，例如B被A吃，C吃A，那么B就吃C！

 对于find函数：

int find(int x)
{if(p[x]!=x){int t=find(p[x]);d[x]+=d[p[x]];p[x]=t;}return p[x];
}

 在寻找根节点和压缩路径优化的同时，我们加入了路径长度计算。整体思想是:

,一开始d[x]表示x到父节点的距离，d[p[x]]表示x父节点到它父节点（根节点）的距离。后面由于路径压缩，我们我们p[x]=root。

d[x]就是x到根节点的路径长度，那么更新一下就是d[x]+=d[p[x]。然后再让p[x]=root.

接下来还有两个问题：

1.X和Y同类判断和处理

        同类首先要判断是不是都在树里，如果都在，就看他们到根节点距离是否相同，相同即为同类。例如x，y那么 (d[x]-d[y])%3 即为同类。如果不在树里，那么我们就要插入到树里，首先让p[x]插入到p[y]下面，并且更新一下绿颜色长度。

 那么绿颜色长度是多少呢？我们可以知道x和y是同类，那么就有一个表达式

∵ (d[x]+?-d[y])%3=0

∴ ?=d[y]-d[x] 即d[p[x]]=d[y]-d[x].

2.X吃Y判断处理

如果都在树里，那么判断(d[x]-d[y]+1)%3即可。（x吃y，那么d[x]应该比d[y]少一，可看图推理）

如果不在树里，那么就要插入,相同问题，绿色区域是多少？

 

 因为x吃y，那么d[x]应该比d[y]少一，那么就有等式

∵ (d[x]+1+?-d[y])%3==0

∴ ?=d[y]-d[x]-1 即d[p[x]]=d[y]-d[x]-1

 240. 食物链 - AcWing题库

#include<iostream>
using namespace std;
const int N=5e5+10;
int p[N],d[N],n,k;
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()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) p[i]=i;int ans=0;while(k--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(x>n || y>n) ans++;else {int px=find(x),py=find(y);if(op==1){if(px==py && (d[x]-d[y])%3) ans++;else if(px!=py){p[px]=py;d[px]=d[y]-d[x];}}else{if(px==py && (d[x]-d[y]+1)%3) ans++;else if(px!=py){p[px]=py;d[px]=d[y]-d[x]-1;}}}}printf("%d\n",ans);return 0;
}