食物链(带权并查集)

题目 题意: 有三类动物，A吃B、B吃C、C吃A。现在给出k句话，判断有多少句话为假话。如果某句话与前边的话形成的条件存在冲突，默认这句话为假，否则为真。 1 x y: x和y为同类 2 x y: x吃y **思路:**维护带权并查集，0:与祖宗同类，1:吃祖宗那一类，2:被祖宗吃。

时间复杂度: O(n + k*α(n)) 代码:

// Problem: 职业玩家
// Contest: QDUOJ
// URL: https://qduoj.com/problem/22Spring10
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;in) {ans ++ ; continue;}
        int u = find(x),v = find(y);
        if(op == 1) //A、B是同类
        {
            if(u == v && ((d[x]-d[y])%3 != 0))
            {
            	ans ++ ;
            }
            else if(u != v)
            {
            	fa[u] = v;
            	d[u] = d[y] - d[x];  
            }
        }
        else
        {
        	if(u == v && ((d[x]-d[y]-1)%3 != 0))
        	{
        		ans ++ ; 
        	}
        	else if(u != v)
        	{
        		fa[u] = v;
        		d[u] = d[y] - d[x] + 1;
        	}
        }
    }
    write(ans);
}
signed main(void)
{  
   T = 1;
   // OldTomato; cin>>T;
   // read(T);
   while(T--)
   {
   	 solve();
   }
   return 0;
}