E - food chain

Portal ： The food chain


The question ： The theme is simple , Just look at the topic directly .
Ideas ： This is a classic weighted search topic .
According to convention , We need two arrays , One is the parent node array p, The other is recording x To p[x] The weight of d[x] Array , Stipulate here x eat p[x].
This question is The difficulty lies in the array of eating and being eaten d The relationship between .
1. If x And y It is the same kind and uses the common ancestor node , Then judge d[x]-d[y])%3 Is it equal to 0, be equal to 0 It means the same as what you said , Otherwise inconsistent ,ans++;
2. If x And y It is the same kind of ancestral node without common use , let px My father node is py, Work out d[px],d[px]=d[y]-d[x];
3. If x eat y And use the common ancestor node , Then judge d[x]-d[y]-1)%3 Is it equal to 0, be equal to 0 It means the same as what you said , Otherwise inconsistent ,ans++;
4. If x eat y And there is no common ancestor node , let px My father node is py, Work out d[px],d[px]=d[y]-d[x]+1;
5. If x,y Greater than n,ans++;
Code ：

#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;
}