https://www.acwing.com/problem/content/description/242/
来源：《算法竞赛进阶指南》, 模板题 , NOI2001 , POJ1182 , kuangbin专题

这道题的方法不唯一，法一：利用并查集维护额外信息（y总讲的）

1. 无论哪种操作，都放在集合中（某种关系）
2. 用每个点和根节点的距离表示和根节点的关系（同类， 被吃， 能吃）
3. 初始化，每个点都是自己树的根节点

把d分成三类

• 余1， 可以吃根节点
• 余2， 可以被根节点吃
• 余0， 和根节点同类
• 但只能记录与父节点距离，路径压缩更新距离

#include <iostream>
using namespace std;
const int N = 50010;
int p[N], d[N];//d[i]的正确理解，应是第 i 个节点到其父节点距离
int n, m;
int find (int x)
{
    if (p[x]!=x)
    {
        int t = find(p[x]);
        d[x]  += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; 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)
              {
                if (px == py && (d[x] - d[y]) % 3) res++;
                else if (px != py)
              {
                p[px] = py;
                d[px] = d[y] - d[x];
               }
            }
            else
            {
            if  (px == py && (d[x] - d[y] - 1)%3)res ++ ;
            else if (px != py)
            {
                p[px] = py;
                d[px] = d[y] + 1 - d[x];
            }

            }
       } 


    }

     printf("%d",res);




    return 0;
}