并查集之边带权

思路：只要有关系，就属于同一个集合，就加入到集合中去（不管是同类or异类）
所以边带权的并查集问题本质上只在维护一个大的集合（其他的都是单个点逐一加到大集合里）

精髓：只要两个元素在同一个集合里，就能通过他们与根节点的距离知道他们之间的关系。

距离的定义

用“距离”来描述关系、判断关系，所有的距离都以根节点为基准，按照mod类别数(3)分为3类。
“距离”：x吃y表示y到x的距离为1. y是第0代，吃y的x是第1代，吃x的是第2代…根节点是第0代
三种关系：用点到根节点之间的距离表示其余根节点之间的关系
mod 3 = 1:可以吃根节点
mod 3 = 2:可以被根节点吃
mod 3 = 0:和根节点同类
把集合中所有的点划分为上述三类。

两个数组的定义：

p[]:父节点,
d[]:到父节点（不是根节点）的距离(初始是1，随着路径压缩会逐渐增大)
我们只能获得点到其直接父节点的距离。路径压缩和更新边权的时候也是这样。

find函数的解释：

int find(int x)
{
    if(p[x] != x){
        int u = find(p[x]); 
        d[x] += d[p[x]]; 
        p[x] = u; 
    }
    return p[x];
}

u = find(p[x])先把父节点及以上压缩到根节点，这时父节点是根节点的一级子节点，x是根节点的二级子节点。过程中d[p[x]]被更新为父节点到根节点的距离。
d[x] += d[p[x]]; p[x] = u;先更新边权，再把x也压到根节点。否则x的父节点到根节点的距离d[p[x]]没加上就丢失了

有同学不明白d[x]到底是到父节点还是根节点的距离：
事实上，d[x]始终代表到父节点的距离，只不过在find之后x的父节点直接变成了祖宗，所以逻辑上成了到祖宗的距离

merge操作的解释：

如果x y的关系是同类且需要merge:[HTML_REMOVED]
同类意味着d[x]+d[px]-d[y])%3 == 0，故有d[px] = d[y] - d[x];
如果x y的关系是x吃y且需要merge:[HTML_REMOVED]
x吃y意味着d[x]-d[y]-1)%3 == 0，故有d[px] = d[y] + 1 - d[x];

题目代码：

#include<iostream>
using namespace std;

const int N = 50010;
int n, k, res;
int p[N]; //父节点
int d[N]; //到父节点的距离

int find(int x)
{
    if(p[x] != x){
        int t = find(p[x]); //先把父节点及以上压缩到树根
        d[x] += d[p[x]]; //更新边权
        p[x] = t; //x节点也压缩到树根
    }
    return p[x];
}
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) p[i] = i;
    while(k--){
        int v, x, y;
        cin >> v >> x >> y;
        if(x > n || y > n) res++;
        else{
            int rx = find(x), ry = find(y);
            if(v == 1){
                //假话
                if(rx == ry && (d[y] - d[x]) % 3) res++;
                //真话
                else if(rx != ry){ //当前不在同一集合中，无法判定为假。故为真，应加入同一集合表示存在同类关系
                    p[rx] = ry;
                    d[rx] = d[y] - d[x]; //(d[x]+d[rx]-d[y])%3 = 0,由于判断时都针对mod 3,故3可省略
                }
            }
            else{ //x吃y
                if(x == y) res++;
                else if(rx == ry && (d[x] - d[y] - 1) % 3) res++; //C++中负数取模得非正数，需要注意别写错
                else if(rx != ry){
                    p[rx] = ry;
                    d[rx] = d[y] + 1 - d[x];
                }
            }
        }
    }
    cout << res << endl;
}