食物链

形式化题目

有 $N$ 只动物编号 $1 \sim N$ ，每只是 A、B、C 三类之一（具体类别未知），三类构成环形食物链：A 吃 B，B 吃 C，C 吃 A。给定 $K$ 句话，每句形如「1 X Y」（X 与 Y 同类）或「2 X Y」（X 吃 Y）。一句话是假话当且仅当满足以下之一：

与前面已确定为真的话冲突；
X 或 Y 的编号大于 $N$ ；
话意是「X 吃 X」。

求 $K$ 句话中假话的总数。

正解

思路

朴素想法：如果对每句话直接检查它之前所有真话的两两关系，最坏 $O(K^2)$ ， $K \leqslant 10^5$ 时约 $10^{10}$ 次操作，不可行。我们需要的其实不是每对动物的关系都显式存下来，而是一个能增量维护"已确认为真的关系集合"并能快速询问任意两只动物当前关系的结构——这正好是带权并查集。

核心建模：给并查集的每条边带上权值 $rel(x) \in \{0,1,2\}$ ，表示 $x$ 相对它父亲的"关系"：

$0$ ： $x$ 与父亲同类；
$1$ ： $x$ 吃父亲；
$2$ ： $x$ 被父亲吃（即父亲吃 $x$ ）。

关键观察是关系在模 3 意义下封闭。设 $r(x)$ 为 $x$ 相对树根的关系（沿路径权值之和模 3），则任意同树两点 $x,y$ 的真实关系为：

rel(x,y) = (r(x) - r(y)) \bmod 3

其中 $0$ 为同类、 $1$ 为 $x$ 吃 $y$ 、 $2$ 为 $y$ 吃 $x$ 。这个减法之所以成立，是因为三条链规则都满足模 3 加法：

已知	已知	合成结果
$x$ 吃 $y$ （ $+1$ ）	$y$ 吃 $z$ （ $+1$ ）	$x$ 吃 $z$ ？不，A 吃 B、B 吃 C 则 C 吃 A，即 $z$ 吃 $x$ （ $1+1 \equiv 2 \pmod 3$ ）
$x$ 吃 $y$ （ $+1$ ）	$y$ 被 $z$ 吃（ $+2$ ）	$x$ 与 $z$ 同类（ $1+2 \equiv 0 \pmod 3$ ）
$x$ 与 $y$ 同类（ $0$ ）	$y$ 吃 $z$ （ $+1$ ）	$x$ 吃 $z$ （ $0+1 \equiv 1 \pmod 3$ ）

模 3 的环正好对应"食物链是三元环"这一题设。

逐句判定：先把第 2、3 类假话（编号越界、X 吃 X）直接判掉；然后对每句话 $d,x,y$ ：

若 $x,y$ 不同根：说明这句话提供全新信息，必为真，用来合并两棵树。设 $w=(d-1+r(y)-r(x)) \bmod 3$ ，把 $x$ 的根挂到 $y$ 的根上、边权为 $w$ ，恰好保证合并后 $(r'(x)-r'(y)) \bmod 3 = d-1$ 。
若 $x,y$ 同根：真实关系为 $(r(x)-r(y)) \bmod 3$ ，若它 $\neq d-1$ 则是假话（ $d-1$ ：同类 $=0$ ， $x$ 吃 $y$ $=1$ ）。

路径压缩：压缩时要把中间节点的 $rel$ 顺手下放为"该节点直接到根"的权值——从根往路径起点逐层累加即可。注意实现顺序的坑：不能在覆盖 rel[x] 之后再读旧值。

样例中三句假话分别为：1 101 1（101 越界）、2 3 3（3 吃 3）、1 1 3（由"1 吃 2、2 吃 3"推出 1 与 3 不是同类）。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 08:10
# update_at: 2026-09-30 08:10

import sys

# parent[x]：x 的父亲；rel[x]：x 到父亲的偏移（0 同类，1 吃父亲，2 被父亲吃）
# 关系在模 3 意义下闭合：同类=0，x 吃 y 记为 (rel 链差) = 1

def find(parent: list[int], rel: list[int], x: int) -> tuple[int, int]:
    """路径压缩版查找：返回 x 的根，以及 x 相对根的关系（模 3）。"""
    path = []
    while parent[x] != x:                  # 第一遍：收集 x 到根路径上的所有点
        path.append(x)
        x = parent[x]
    root = x
    r = 0
    for node in reversed(path):            # 第二遍：从根往下算偏移并压缩
        r = (r + rel[node]) % 3            # node 到根 = node 到父亲 + 父亲到根
        parent[node] = root
        rel[node] = r
    return root, r                         # r 此刻正是最外层 x（路径起点）到根的偏移


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    k = next(data)

    parent = list(range(n + 1))            # 一开始每个动物自成一个集合
    rel = [0] * (n + 1)                    # 自己到自己当然是同类
    lies = 0
    for _ in range(k):
        d, x, y = next(data), next(data), next(data)
        out_of_range = x > n or y > n
        self_eaten = d == 2 and x == y
        if out_of_range or self_eaten:
            lies += 1
            continue
        rx, rxy_x = find(parent, rel, x)   # rxy_x：x 相对根的关系
        ry, rxy_y = find(parent, rel, y)
        if rx != ry:                        # 两棵树尚未连通，本句必为真，用来合并
            # 需满足 (x 相对新根) = (y 相对新根) + w，即 w = d-1 + rxy_y - rxy_x
            w = (d - 1 + rxy_y - rxy_x) % 3
            parent[rx] = ry
            rel[rx] = w
        else:
            # 已同根：真实关系差 = (x 相对根) - (y 相对根)
            truth = (rxy_x - rxy_y) % 3
            if truth != d - 1:              # d-1：同类=0，x 吃 y=1
                lies += 1

    print(lies)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 00:33
 * update_at: 2026-10-05 00:33
 */

// 食物链：带权并查集（种类并查集）
// 每只动物相对父亲记录一个模 3 关系：0 同类、1 吃父亲、2 被父亲吃。
// 三类动物的环形食物链正好对应模 3 加法，于是「同类 / x 吃 y」统一成一次减法判断。

#include <cstdio>

typedef long long ll;

const int MAXN = 50005;  // n <= 50000

int fa[MAXN];    // fa[x]：x 的父亲，自成一集时指向自己
int rel[MAXN];   // rel[x]：x 相对父亲的关系（0 同类，1 x 吃父亲，2 父亲吃 x）
int siz[MAXN];   // siz[根]：集合大小，按大小合并以控制树高

// 查根并把 x 到根的路径压缩；返回根，同时让 rel[x] 变成 x 相对根的关系。
// 注意顺序：先递归让父亲指向根、父亲的关系更新到位，再累加 rel[x]。
int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    int root = find(fa[x]);
    rel[x] = (rel[x] + rel[fa[x]]) % 3;  // x 到根 = x 到父亲 + 父亲到根
    fa[x] = root;
    return root;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        rel[i] = 0;
        siz[i] = 1;
    }

    int lie_count = 0;  // 假话总数
    for (int t = 0; t < k; t++) {
        int d, x, y;
        scanf("%d %d %d", &d, &x, &y);

        // 越界，或者说出「x 吃 x」，直接是假话
        if (x > n || y > n || (d == 2 && x == y)) {
            lie_count++;
            continue;
        }

        int rootx = find(x);
        int rx = rel[x];  // x 相对根的关系
        int rooty = find(y);
        int ry = rel[y];  // y 相对根的关系

        if (rootx != rooty) {
            // 两棵树还没连通，这句话必为真，用它把两棵树合并。
            // 合并的目标是让 (rx' - ry') mod 3 == d-1（同类为 0，x 吃 y 为 1）。
            if (siz[rootx] < siz[rooty]) {
                // 把 rootx 挂到 rooty 下，此时 x 到新根为 rx + rel[rootx]
                fa[rootx] = rooty;
                rel[rootx] = ((d - 1 + ry - rx) % 3 + 3) % 3;
                siz[rooty] += siz[rootx];
            } else {
                // 把 rooty 挂到 rootx 下，此时 y 到新根为 ry + rel[rooty]
                fa[rooty] = rootx;
                rel[rooty] = ((rx - ry - (d - 1)) % 3 + 3) % 3;
                siz[rootx] += siz[rooty];
            }
        } else {
            // 已同根：真实关系为 (rx - ry) mod 3，与话意不符则是假话
            int truth = ((rx - ry) % 3 + 3) % 3;
            if (truth != d - 1) {
                lie_count++;
            }
        }
    }

    printf("%d\n", lie_count);
    return 0;
}

复杂度

时间： $O(K \cdot \alpha(N))$ ，路径压缩下均摊近似线性；
空间： $O(N)$ 。

总结

本题是「带权并查集（种类并查集）」的模板题。要点有两个：一是把环形三元关系编码成模 3 加法，使"同类/吃/被吃"三种判断统一成一次减法；二是路径压缩时边权要同步下放。数据全部真实测试通过。

图示解析

样例中关系树的合并过程

以样例第 2、3、5 句为例展示并查集树的形态与边权含义（边权 0 同类、1 子吃父、2 父吃子）：

graph TD
    subgraph after["句 2-3 后（2 吃 3，1 吃 2，根为 3）"]
        n3["3 (根)"] -->|""| n2["2, rel=1 (2 吃 3)"]
        n2 -->|""| n1["1, rel=1 (1 吃 2)"]
    end

节点标注了各自的 $rel$ 值。此时 $r(1) = (1+1) \bmod 3 = 2$ ， $r(3)=0$ ，故 $rel(1,3) = (2-0) \bmod 3 = 2 \neq 0$ ：第 5 句「1 1 3 同类」与已有真话冲突，判为假话——这正是输出 3 句假话中的最后一句。整棵树上任意两点的真假判定都只需要各一次 find 加一次模 3 减法。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

样例中关系树的合并过程