又来重温一下这个经典的带权并查集题目。

本题的关系有三层 -> a -> b -> c -> ，但不同的是本题的关系是有向的，也就是说a和b如果是敌对关系，那么b和a就不是敌对关系。所以反向推算关系不是简单的相加。

关系传递的本质实际上是向量的运算。

还是设 d[x] 表示 x 与 fa[x] 的关系，0 代表是同类，1 代表是x吃fa[x], 根据关系图自然2就代表x被fa[x]吃。

下面假设a的祖先是x，b的祖先是y，为简化书写，设他们的向量关系为

\vec{a} = (a,x) \quad \vec{b} = (b,y)
给出的关系设为rel = \vec{ab}

以下的向量关系均用以上符号代替，实际运算时自行带入二元组运算即可

1. 若x = y
   想要知道 \vec{ab} ，则需要 \vec{a} – \vec{b} 然后对3取模并移动到正整数
   此时得到的关系0代表ab是同类，1代表a吃b，2代表a被b吃。直接与rel进行比较即可。

2. 如果x和y不等，那么这个给出的关系肯定是合法的
   合并的时候同样fa[x] = y，\vec{x} = \vec{b} + \vec{ab} – \vec{a}

然后就可以愉快的搞了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 233;
int fa[maxn], d[maxn];
int ff(int x)
{
    if(fa[x] == x) return x;
    int r = ff(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = r;
}
int main()
{
    int n,k; cin >> n >> k;
    for(int i = 0; i <= n; i++) fa[i] = i;
    int ans = 0;
    for(int i = 1; i <= k; i++)
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if(a > n || b > n) {ans ++; continue;}
        else if(t == 2 && a == b) {ans++; continue;}
        else
        {
            int rel;
            if(t == 2) rel = 1;
            else rel = 0;
            int x = ff(a), y = ff(b);
            if(x == y) 
            {
                if((((d[a] - d[b]) % 3) + 3) % 3 != rel)
                ans++;
            }
            else
            {
                fa[x] = y;
                d[x] = d[b] - (d[a] - rel);
            }
        }
    }
    cout<< ans;
}