食物链

老虎、狗和马，它们之间有个奇怪的“循环吃法”：

老虎吃狗，狗吃马，马吃老虎。

现在，森林里来了一个“神秘法官”，他把 N 只动物（编号 1~N）关在小黑屋里，你只能透过门缝听，完全看不到谁是谁。法官开始念“内部情报”：

• 情报一：1 X Y —— 意思是“X 和 Y 是同一个物种”（比如都是老虎）。
• 情报二：2 X Y —— 意思是“X 能吃掉 Y”。

你的任务就是当“鉴谎官”：每听到一句话，就判断它是否和前面已经确认的情报逻辑矛盾，要是矛盾，这就是假话。最后统计一共听到了多少句假话。

为什么我们不能直接“看答案”？

你肯定想：“把门打开看看它是老虎还是狗不就行了？”

关键就在这里：法官永远不让你开门，而且他给的情报特别少！ 比如他说“1号吃2号，2号吃3号”，虽然不知道 1、2、3 具体是谁，但我们能铁定推出“3号一定吃1号”（因为老虎→狗→马→老虎，循环了）。这时候如果法官补一句“1号和3号是同类”，那肯定是假话——因为我们用逻辑推导出它俩是“食物链上下游”，绝不可能是同类。

所以，我们的核心思路不是去猜“1号是老虎还是狗”，而是只维护动物之间两两的“相对关系”：是同类？还是甲吃乙？

第一关：先忘掉“吃”，只谈“同类”

假设所有情报都是“X和Y是同类”，那问题就简单多了：就像在交朋友，A和B是朋友，B和C是朋友，那A和C自然也是朋友。随着情报增多，动物们会分成一个个“朋友圈”。

这时候，我们需要一个超级小本本，它能快速做到两件事：

1. 查（Find）：任意两只动物，查一查它们在不在同一个朋友圈？
2. 并（Union）：如果不在同一个朋友圈，怎么把这两个圈子快速合并成一个？

这个“超级小本本”，就是算法界大名鼎鼎的并查集（Union-Find）。你可以把它想象成一棵棵“家族树”：

• 每个朋友圈选一个“族长”（根节点），比如 1 号是族长。
• 每个成员只记录自己的“老爸”是谁（父节点 f[i]）。
• 想找族长，就顺着老爸、老爸的老爸……一路往上爬。

并查集的核心操作

1. 查询族长（Find）——加上“路径压缩”

如果一条链特别长（1是族长，2挂1，3挂2，4挂3……），找4的族长要爬三层，太慢了！ 所以我们的绝招是：在找族长的时候，顺手把沿途所有人的老爸直接改成族长。下次再找，一步到位！

int find(int x) {
    if (f[x] == x) return x;    // 我自己就是族长
    return f[x] = find(f[x]);   // 路径压缩：直接把老爸改成族长
}

2. 合并圈子（Union）——加上“按秩合并”

如果两个圈子要合并，该让哪个圈子的族长当新族长呢？如果总把大树挂在小树上，树会越来越高。

所以我们记录每棵树的高度（rank），总是把矮的树挂到高的树下面，这样树的高度增长最慢，整体更扁平。

void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) swap(ra, rb); // 让ra当新族长
    f[rb] = ra;                             // rb挂到ra下面
    if (rank[ra] == rank[rb]) rank[ra]++;  // 高度一样时，新高度+1
}

有了路径压缩和按秩合并，并查集的速度就快到飞起（几乎是常数时间 O(α(N))），处理几万只动物绰绰有余。

第二关：加入“吃”的关系——带上“权值”的小本本

现在问题升级了，圈子里不仅有“同类”，还有“上级”和“下级”（吃与被吃）。普通并查集只记录“连不连”，现在我们要记录“连着的这条线是什么关系”。

于是，我们给并查集的每条边贴上一个标签（权值）dis[i]，表示 i 和它的老爸 f[i] 之间的关系。我们用数字 0、1、2 来定义：

• 0：我和老爸是同类。
• 1：老爸吃我。（重点！代码里就是这么定义的，记牢它）
• 2：我吃老爸。

为什么要用 0、1、2？因为三种关系首尾相连（0→同类，1→老爸吃我，2→我吃老爸），正好可以用模 3（%3）加法来传递。比如：如果老爸吃我（1），老爸的老爸吃老爸（1），那我到爷爷的关系就是 (1+1)%3 = 2，表示我吃爷爷。完美契合循环食物链！

带权并查集的“查”（Find）——边压缩边算账

在找族长（根节点）的路上，我们要把沿途的权值累加起来，这样就能知道我和族长是什么关系。

int find(int x) {
    if (f[x] == x) return x;
    int fa = f[x];           // 记下老爸
    int root = find(fa);     // 递归找到族长（同时更新了dis[fa]）
    dis[x] = (dis[x] + dis[fa]) % 3; // 累加关系：我到老爸 + 老爸到爷爷
    return f[x] = root;      // 路径压缩，挂到族长下面
}

带权并查集的“并”（Union）——最精彩的公式推导

现在，我们听到一句新情报：“X 和 Y 的关系是 d”（d=0 代表同类，d=1 代表 X 吃 Y）。

第一步：找族长 找到 X 的族长 fx，Y 的族长 fy。 如果 fx == fy，说明它们已经在同一本账上了，我们直接算一下 X 和 Y 的实际关系，跟 d 比对，对不上就是假话（后面细说）。

第二步：合并账本 如果 fx != fy，说明这句话不矛盾，是真的。我们要把两本账合并。假设我们把 fy 这棵树的族长，挂到 fx 下面（即 f[fy] = fx）。

现在最关键的问题来了：新挂上去的这条边，标签 dis[fy] 应该填几？

我们来解这个“模 3 方程”：

• 已知 dis[x] 表示 X 和老爸 fx 的关系（老爸吃我？还是我吃老爸？）。
• 已知 dis[y] 表示 Y 和老爸 fy 的关系。
• 设 dis[fy] = w，表示 fy 和它新老爸 fx 的关系。

我们要让合并后，X 和 Y 的关系正好等于 d（d=1 时 X 吃 Y）。

根据我们的定义，任意两个动物 a 和 b 的关系（a 吃 b 则值为1），可以用公式计算：a 到 b 的关系 = (dis[b] - dis[a] + 3) % 3

所以，X 到 Y 的关系等于：(dis[y] 到 fx的关系 - dis[x] + 3) % 3

而 Y 到 fx 的关系，就是 Y 先到 fy，再从 fy 到 fx： (dis[y] + dis[fy]) % 3

代入得到： ((dis[y] + w) - dis[x]) % 3 = d

解这个方程（把 w 挪到一边）： w = (dis[x] - dis[y] + d + 3) % 3

看！这就是参考答案里那行公式 dis[fb] = (3 + dis[a] - dis[b] + d) % 3 的由来！ 它完全不是凭空出现的，而是逻辑推导的必然结果。

第三关：如何当场判定假话？

每次听到一句话，我们按以下顺序排查：

1. 硬伤：如果 X 或 Y 编号大于 N 或者小于等于 0，直接算假话（范围外不存在）。
2. 自己吃自己：如果 op == 2 且 X == Y，直接算假话（动物不能自己吃自己，但自己和自己同类是真话）。
3. 逻辑冲突（已经在同一个集合中）：

  * 如果是“同类”（op=1）：检查 dis[x] 是否等于 dis[y]。如果不等，说明它们对族长的关系不同，不可能是同类，假话！
  * 如果是“X吃Y”（op=2）：计算 X 到 Y 的实际关系 (dis[y] - dis[x] + 3) % 3，看它是否等于 1。如果不等于 1，假话！

如果以上都没问题，这句话就是真话，执行 merge 操作，把两个集合连起来。

回头看看代码，是不是全懂了？

最后，我们带着满满的成就感，再看一遍参考答案：

#include <bits/stdc++.h>
#define MAXN 50005
using namespace std;
int n, k, f[MAXN], dis[MAXN], x, y, op, ans;
int find(int x)
{
  if (f[x] == x)
    return x;
  int fa = find(f[x]);
  dis[x] = (dis[x] + dis[f[x]]) % 3;
  return f[x] = fa;
}
void merge(int d, int a, int b)
{
  int fa = find(a), fb = find(b);
  if (fa == fb)
    return;
  dis[fb] = (3 + dis[a] - dis[b] + d) % 3;
  f[fb] = fa;
}
int main()
{
#ifndef ONLINE_JUDGE
  freopen("data/data1.in", "r", stdin);
// freopen("data/data1.out", "w", stdout);
#endif
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++)
    f[i] = i;
  while (k--)
  {
    scanf("%d%d%d", &op, &x, &y);
    if (x > n || x <= 0 || y > n || y <= 0)
    {
      ans++;
      continue;
    }
    if (op == 1)
    {
      if (find(x) == find(y))
        ans += dis[x] != dis[y];
      else
        merge(op - 1, x, y);
    }
    else
    {
      if (find(x) == find(y))
        ans += (dis[y] - dis[x] + 3) % 3 != 1;
      else
        merge(op - 1, x, y);
    }
  }
  printf("%d", ans);
  return 0;
}

• f 数组是“家族树”的骨架。
• dis 数组是“家族树”边上的关系标签。
• find 函数里的递归，是在“寻根问祖”的同时“清理门户”（路径压缩+权值更新）。
• merge 里的公式，是在两个陌生的家族之间，找到唯一正确的“联姻方式”。

并查集就像一位精明的档案管理员，用“路径压缩”让查档案快如闪电，用“按秩合并”让档案柜永远整整齐齐。而带权并查集，则是给每份档案贴上了“关系标签”，让老虎、狗、马之间的恩恩怨怨，都在 0、1、2 的模 3 运算中灰飞烟灭。

现在，打开你的编辑器，亲手敲一遍吧。当代码跑出正确答案的那一刻，你收获的不仅仅是一道题的通过，更是一种将“复杂关系”抽象成“数学运算”的神奇思维。