自己一开始很难理解的点都做了注释，方便将来回忆。

主要参考了ITNXD写的题解，并加入了自己的一些理解。

C++ 代码

#include <iostream>

using namespace std;

const int N = 5e4 + 10;

// p[]：存储父节点
// d[]：存储到父节点的距离
int p[N], d[N];

// 这一段注释参考：https://www.acwing.com/solution/content/19133/
// 根据题意：四个动物构成食物链 1->2->3->4 则1 4 为同类 （即 1 2 3, 2 3 4都是一个食物链）
// （都进行模3取余操作）
// 距离为d + 1的点吃距离为d的点
// 与根节点距离相同：为同类
// 与根节点距离差一：为 x -> y（x吃y）
// 与根节点距离差二：为 y -> x（y吃x）

// 核心：不仅返回x的根节点，而且向上一路压缩，让路径上的所有节点都指向根节点
int find(int x) {
    // x不是根节点
    if (x != p[x]) {
        // 向上找x的父节点p[x]的根节点并一路压缩，让路径上的所有节点都指向根节点并更新d为到根节点的距离
        int t = find(p[x]);
        // 当退出上一层的递归时，上一层会指向根节点，即p[x]指向根节点，也就是说p[x]的父节点为根节点，所以d[p[x]]为p[x]到根节点的距离
        d[x] += d[p[x]];
        // x指向根节点，完成路径压缩
        p[x] = t;
    }
    return p[x];
}

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        p[i] = i;

    int res = 0;
    while (k--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (x > n || y > n) res++;
        else {
            int px = find(x), py = find(y);
            if (t == 1) {
                // x和y在同一链上，因此可以判断出它们的关系
                // t == 1断言x和y是同类，则x和y之间的距离应该是3的倍数，否则就是假话
                if (px == py && (d[x] - d[y]) % 3) { // x和y之间的距离mod 3之后如果不是0则为假话
                    res++;
                } else if (px != py) {
                    // x和y不在同一链上，则合并这两条链，将y的祖先py升一级，成为x的祖先px的爸爸
                    p[px] = py;
                    // 因为只要不和之前的话矛盾就默认是真话，所以要让t == 1，即“x和y是同类”成立
                    // 于是，(d[x] + d[px] - d[y]) % 3 == 0
                    d[px] = d[y] - d[x];
                }
            } else {
                // t == 2断言x->y，因此x到根节点的距离应该比y多1或4,7,...，即(d[x] - d[y] - 1) % 3 == 0，否则就是假话
                if (px == py && (d[x] - d[y] - 1) % 3) {
                    res++;
                } else if (px != py) {
                    p[px] = py;
                    // 要让t == 2，即“x吃y”成立
                    // 于是，(d[x] + d[px] - d[y] - 1) % 3 == 0
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }

    }

    cout << res << endl;

    return 0;
}