题目
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int n, k;
int p[N], d[N];
int find(int x)
{if(p[x] != x){int root = find(p[x]);d[x] += d[p[x]];p[x] = root;}return p[x];
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n; i++) p[i] = i;int res = 0;cin >> k;while(k--){int t, a, b;cin >> t >> a >> b;if(a > n || b > n){res++;continue;}int pa = find(a), pb = find(b);if(t == 1){if(pa == pb && (d[a] - d[b]) % 3) res++;else if(pa != pb){p[pa] = pb;d[pa] = d[b] - d[a];}}else{if(pa == pb && (d[a] - d[b] - 1) % 3) res++;else if(pa != pb){p[pa] = pb;d[pa] = d[b] - d[a] + 1;}}}cout << res;return 0;
}注意
1.边界判断别漏
2.涉及到distance的问题，pa == pb且不矛盾的情况不能简单归类为else，不然d[pa]会发生实际变化
思考
关于存储
策略为通过相对距离存储关系
对于a, b
d[a] = d[b]
对应d[pa] = d[b] - d[a]；
首先pa和b距离pb同一长度，然后减小pa与a的间距d[a]，导致a与b同一权重（别管pa，pa肯定离pb更近了）
同理
对于a, b
d[a] = d[b] + 1
对应d[pa] = d[b] - d[a] + 1
一句话：最主要是在相对距离的玩法下，增加pa距离父节点的距离，就等于增加a距离根节点的距离。
关于使用
pa与pb不相等，说明a, b关系此前不存在（即便间接a, x x,y也没有）
因此将pa树纳入pb下，并对于a, b进行距离调整
最后可预见的是一片关系森林，每个size > 1树上的元素a, b都有一个基本的性质（pa == pb）
size = 1的树肯定找不到pa == pb的情况，由此区分有旧关系，和新关系。
举例判定2类型矛盾的代码
在有旧关系的基础上，不满足(d[a] - d[b] - 1) % 3的情况（之前有关系，和现在的不矛盾）只有当d[a] - d[b]的差模3余1（代表a吃b）。
也即考虑加粗部分在不矛盾的情况下模3余0即可得到代码。
