具体：基础班笔记P186—（Y总说这是并查集最难的题目之一了）
模板题：836合并集合、837连通块中点的数量（维护集合size的并查集）本题是维护到祖宗节点距离的并查集
并查集模板：基础班笔记P38
参考题解：松鼠的图不错

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;
int n, m;
int p[N], d[N];

int find(int x) { 
    if (p[x] != x) { //这里不能直接按照模板给的 p[x] = find(p[x]); 因为p[x]存的就不是x的父节点，而是x的祖宗节点
        int t = find(p[x]);
        d[x] += d[p[x]]; //这里d[i]表示i到它父节点的距离
        p[x] = t;
    }
    return p[x];
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) p[i] = i;
    int res = 0;
    while (m --) {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if (x > n || y > n) res ++;
        else {
            int px = find(x), py = find(y);
            if (t == 1) { //根据输入表示如果x, y是同一类
                if (px == py && (d[x] - d[y]) % 3) res ++; //当x y在同一个集合且x可以吃y则说明是假话，因为同一类不可以吃，只有d[x]-d[y]%3==0才是真话
                else if (px != py) { //当x y不在同一个集合，将x接到y上，让x的根节点做y的根节点的儿子p[px] = py;
                    p[px] = py;
                    d[px] = d[y] - d[x]; //这里的d[px]是我们自己定义的，当(d[x]+?)%3==d[y]%3时是真话！---> ?=d[px]=d[y] - d[x]
                }
            } 
            else { // 这里表示x y不同类
                if (px == py && (d[x] - d[y] - 1) % 3) res ++; //x y在一个集合，且x吃y，说明x到根节点的距离比y到根节点的距离要多1，d[x]-d[y]-1)%3==0才是真话，否则是假话
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] - d[x] + 1; //不在同一个集合，则定义?--> d[px]满足(d[x]+?-d[y]+1)%3==0
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}