【食物链】

题目

代码

#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即可得到代码。