E - 食物链

传送门：食物链


题意：题意简单，直接看题目即可。
思路：这是个经典的带权并查集题目了。
根据惯例，我们需要两个数组，一个是父亲节点数组p，另一个为记录x到p[x]的权值的d[x]数组，在这里规定x吃p[x]。
这道题的难点在于吃与被吃的数组d之间的关系。
1.假如x与y是同类且用共同的祖宗节点，那么就判定d[x]-d[y])%3是否等于0，等于0就代表与所说的话一致，反之不一致，ans++;
2.假如x与y是同类且没用共同的祖宗节点，就让px的父亲节点为py，算出d[px]，d[px]=d[y]-d[x];
3.假如x吃y且用共同的祖宗节点，那么就判定d[x]-d[y]-1)%3是否等于0，等于0就代表与所说的话一致，反之不一致，ans++;
4.假如x吃y且没用共同的祖宗节点，就让px的父亲节点为py，算出d[px]，d[px]=d[y]-d[x]+1;
5.假如x,y大于n，ans++;
代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=5e4+5;
int p[N],d[N];
int find(int x)
{
	if(x!=p[x]) 
	{
		int t=find(p[x]);
		d[x]+=d[p[x]];
		p[x]=t;
	}
	return p[x];
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i = 1; i <= n; i ++ ) p[i] = i;
	int ans=0;
	while(k--)
	{
		int t,x,y;
		scanf("%d%d%d",&t,&x,&y);
		int px=find(x),py=find(y);
		if (x > n || y > n) ans ++ ;
		else
		{
			if(t==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",ans);
	return 0;
}