AtCoder Beginner Contest 437 题解

项目	内容
比赛时间	2025-12-20
比赛链接	https://atcoder.jp/contests/abc437
题目数量	A–G 共 7 题

比赛概览

本场整体难度中等偏基础。A、B 是纯送分题（单位换算与简单计数）；C 是一道经典的贪心转化题，把"拉的强度够不够拉坐的重量"巧妙地变形为背包式预算问题；D 是排序 + 前缀和的绝对值求和套路题；E 需要看出序列的递推构造本质就是一棵字典树，较有思维含量；F 是"曼哈顿距离旋转 45°"的经典技巧配合线段树；G 是最难的压轴题，需要最大流建模来判定可行性与构造删除顺序。值得重点掌握的是 C 的贪心转化、D 的绝对值前缀和技巧、E 的 Trie 排序、F 的坐标旋转变换，以及 G 的流建模思路。

---

A - Feet

题目链接：https://atcoder.jp/contests/abc437/tasks/abc437_a

题目大意

已知 $1$ 英尺等于 $12$ 英寸。给定两个整数 $A$（英尺数）和 $B$（英寸数），输出 $A$ 英尺 $B$ 英寸一共是多少英寸（不输出单位）。数据保证 $1 \le A \le 8$，$0 \le B \le 11$。

思路

这是一道简单的单位换算题。$1$ 英尺 $= 12$ 英寸，因此把 $A$ 英尺换算成英寸后再加上 $B$ 即可：

$$A\text{ 英尺 }B\text{ 英寸} = 12A + B\text{ 英寸}.$$

需要注意 $B$ 可以为 $0$（此时答案是 $12A$），但这并不影响计算。直接读入两个整数、输出 $12A+B$ 即可，无任何坑点。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    cin >> a >> b;
    cout << a * 12 + b << '\n';
    return 0;
}

官方题解还给出了 Python 写法：

a, b = map(int, input().split())
print(a * 12 + b)

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

B - Tombola

题目链接：https://atcoder.jp/contests/abc437/tasks/abc437_b

题目大意

有一个 $H$ 行 $W$ 列的网格，每个格子上写着一个互不相同的整数 $A_{i,j}$。主持人喊出了 $N$ 个互不相同的整数 $B_1,\dots,B_N$。对每一行，统计该行中一共有多少个数字被主持人喊到，求这些统计值的最大值。

思路

这题没有任何技巧，按题意直接模拟即可。由于所有数的取值范围都很小（$A_{i,j}, B_i \le 90$），可以用一个布尔数组（或 set）来标记哪些数被喊到：

1. 读入网格 $A$；
2. 读入 $B_1,\dots,B_N$，把 $B_i$ 标记为"被喊到"；
3. 对每一行 $i$，用计数器 $cnt$ 统计该行中满足"被喊到"的格子数，并用 $ans=\max(ans,cnt)$ 更新答案。

数据范围极小（$H \le 3$，$W \le 5$，$N \le 90$），即使朴素地对每个格子再枚举 $N$ 个数判断是否存在，复杂度也只有 $O(HWN)$，同样可以通过。用布尔数组可以更直接地把单次判定降到 $O(1)$。

注意题目保证网格内所有数互不相同、$B_i$ 也互不相同，所以每个格子至多匹配一个 $B_i$，不会出现重复计数的问题。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int h, w, n;
    cin >> h >> w >> n;

    vector<vector<int>> a(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) cin >> a[i][j];
    }

    vector<bool> called(91, false);   // 被喊到的数标记
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;
        called[b] = true;
    }

    int ans = 0;
    for (int i = 0; i < h; i++) {
        int cnt = 0;
        for (int j = 0; j < w; j++) {
            if (called[a[i][j]]) cnt++;
        }
        ans = max(ans, cnt);
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(HW + N)$（布尔数组标记）
• 空间复杂度：$O(91 + HW)$

---

C - Reindeer and Sleigh 2

题目链接：https://atcoder.jp/contests/abc437/tasks/abc437_c

题目大意

有 $N$ 头驯鹿和一辆雪橇，第 $i$ 头驯鹿有重量 $W_i$ 和力量 $P_i$。每头驯鹿要么"拉雪橇"，要么"坐雪橇"。要求所有拉雪橇的驯鹿的总力量不小于所有坐雪橇的驯鹿的总重量。问最多可以让多少头驯鹿坐在雪橇上。共有 $T$ 组测试数据。

思路

设坐雪橇的驯鹿集合为 $S$。则条件为"拉雪橇的总力量 $\ge$ 坐雪橇的总重量"：

$$\sum_{i \notin S} P_i \ge \sum_{i \in S} W_i.$$

利用 $\sum_{i \notin S} P_i = \sum_{i=1}^{N} P_i - \sum_{i \in S} P_i$，把条件变形为

$$\sum_{i \in S} (W_i + P_i) \le \sum_{i=1}^{N} P_i.$$

这个变形是本题的关键：右边是一个与 $S$ 无关的常数（可以看作预算 $B=\sum P_i$），而左边每一项对集合的"成本"是 $W_i+P_i$。于是问题变成了：

有 $N$ 个物品，第 $i$ 个物品的大小为 $s_i = W_i+P_i$，在总大小不超过 $B$ 的前提下，最多能选多少个物品？

这是经典的"预算内选最多"贪心问题。对所有物品按 $s_i$ 升序排序，然后从小到大依次累加，直到累加和将要超过 $B$ 为止，累加成功的个数即为答案。

贪心正确性：对任意 $k$ 个物品，其大小之和最小当且仅当选的是 $k$ 个最小的 $s_i$（因为交换论证：若某个选中物品 $a$ 的大小大于某个未选中物品 $b$ 的大小，则把 $a$ 换成 $b$ 不会使总和变大）。因此若前 $k$ 个最小值的和 $\le B$，则选 $k$ 个可行；反之任何 $k$ 个物品的和都 $\ge$ 前 $k$ 个最小值的和 $> B$，选 $k$ 个不可行。故按序贪心到不能加为止，答案就是最大的可行 $k$。

边界情况：所有 $W_i \ge 1$，所以 $S$ 为全集时左边 $=\sum(W_i+P_i)=\sum P_i + \sum W_i > \sum P_i$，恒不可行，即答案至多为 $N-1$；当没有任何一头能坐上时输出 $0$。实现时注意用 long long，因为 $\sum P_i$ 最多可达 $3\times 10^5 \times 10^9 = 3\times 10^{14}$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        vector<long long> wp(n);
        long long budget = 0;          // 所有驯鹿的总力量 sum(P_i)
        for (int i = 0; i < n; i++) {
            long long w, p;
            cin >> w >> p;
            wp[i] = w + p;             // 坐上雪橇的"成本"
            budget += p;
        }

        sort(wp.begin(), wp.end());

        long long cur = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (cur + wp[i] <= budget) {
                cur += wp[i];
                ans++;
            } else {
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

官方题解给出的 Python 实现（整理为更清晰的写法）：

def solve():
    n = int(input())
    wp = [tuple(map(int, input().split())) for _ in range(n)]
    wp.sort(key=lambda x: x[0] + x[1])      # 按 W_i + P_i 排序
    total_p = sum(p for _, p in wp)          # 总力量预算
    cur = 0
    ans = 0
    for w, p in wp:
        if cur + w + p <= total_p:
            cur += w + p
            ans += 1
        else:
            break
    print(ans)

for _ in range(int(input())):
    solve()

复杂度分析

• 时间复杂度：$O(N \log N)$（排序是瓶颈；单组测试）
• 空间复杂度：$O(N)$

---

D - Sum of Differences

题目链接：https://atcoder.jp/contests/abc437/tasks/abc437_d

题目大意

给定长度分别为 $N$、$M$ 的正整数序列 $A=(A_1,\dots,A_N)$ 和 $B=(B_1,\dots,B_M)$，求

$$\sum_{i=1}^{N}\sum_{j=1}^{M}|A_i-B_j| \pmod{998244353}.$$

思路

绝对值是有方向的：$|x-y|=x-y$（当 $x\ge y$）或 $y-x$（当 $x<y$）。这提示我们把每个 $B_j$ 的贡献按 $A_i$ 与 $B_j$ 的大小关系拆成两部分来计算。

先把 $A$ 排序成升序（排序不改变答案，只是让"小于/大于等于"变得容易定位）。固定一个 $B_j=y$，设 $p$ 为 $A$ 中第一个满足 $A_p \ge y$ 的下标（即 lower_bound 的位置，若所有 $A_i<y$ 则 $p=N$）。那么：

• 对满足 $A_i < y$ 的 $i$（共 $p$ 个，下标 $0,\dots,p-1$），贡献为 $y-A_i$，总和为

  $$\sum_{A_i < y}(y-A_i) = p\cdot y - \sum_{i=0}^{p-1} A_i.$$

• 对满足 $A_i \ge y$ 的 $i$（共 $N-p$ 个），贡献为 $A_i-y$，总和为

  $$\sum_{A_i \ge y}(A_i-y) = \sum_{i=p}^{N-1} A_i - (N-p)\cdot y.$$

于是只要预处理 $A$ 的前缀和 $\mathrm{pre}[i]=\sum_{t=0}^{i-1}A_t$，就有：

$$\sum_{i=0}^{p-1} A_i = \mathrm{pre}[p], \qquad \sum_{i=p}^{N-1} A_i = \mathrm{pre}[N] - \mathrm{pre}[p].$$

对每个 $B_j$ 用二分（lower_bound）找出 $p$，即可在 $O(\log N)$ 内算出该 $B_j$ 的全部贡献，累加到答案。

正确性：以上拆分把每个绝对值按照"谁大谁小"确定符号后求和，与定义式逐项一致，没有重复也没有遗漏。

实现细节与易错点：

1. 必须在计算过程中就取模，并且最终把答案归一到 $[0, MOD)$。减法可能出现负数，需要加模处理：(x - y + MOD) % MOD。
2. 用 long long：$A_i,B_j$ 可达 $10^9$ 量级，$N,M$ 可达 $3\times 10^5$，乘积与累加都会超出 int。

（官方题解等价地维护了前后缀和数组并对每个 $B_j$ 二分，本解与其思想完全一致。）

参考代码

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    vector<long long> pre(n + 1, 0);          // pre[i] = a[0] + ... + a[i-1]
    for (int i = 0; i < n; i++) {
        pre[i + 1] = (pre[i] + a[i]) % MOD;
    }

    long long ans = 0;
    for (int j = 0; j < m; j++) {
        long long y;
        cin >> y;

        int p = (int)(lower_bound(a.begin(), a.end(), y) - a.begin()); // 第一个 >= y 的下标

        // A_i < y : (y - A_i) 的和
        long long low = ((long long)p % MOD) * (y % MOD) % MOD;
        low = (low - pre[p] + MOD) % MOD;

        // A_i >= y : (A_i - y) 的和
        long long high = (pre[n] - pre[p] + MOD) % MOD;
        high = (high - ((long long)(n - p) % MOD) * (y % MOD) % MOD + MOD) % MOD;

        ans = (ans + low + high) % MOD;
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N\log N + M\log N)$（排序 + 每个 $B_j$ 二分一次；等价地也可写成 $O((N+M)\log(N+M))$）
• 空间复杂度：$O(N)$

---

E - Sort Arrays

题目链接：https://atcoder.jp/contests/abc437/tasks/abc437_e

题目大意

有 $N+1$ 个序列 $A_0,A_1,\dots,A_N$。$A_0$ 是空序列；对每个 $i\ge 1$，$A_i$ 是在 $A_{x_i}$（$0\le x_i<i$）的末尾追加一个整数 $y_i$ 得到的。把 $A_1,\dots,A_N$ 按字典序排序（相等的序列按下标从小到大排），输出排列 $P$（即排好后各序列对应的下标序列）。

思路

关键观察：序列 $A_i$ 的定义方式——"在 $A_{x_i}$ 末尾追加 $y_i$"——恰好构成一棵字典树（Trie）结构。$A_i$ 就是根节点沿 $y$ 值路径走到某个节点所代表的前缀序列。若两个序列完全相同，则它们落在同一个 Trie 节点上。

建树：每个节点维护两部分信息：

• 孩子表：用 map<int,int>（键为边上的值 $y$，值为子节点编号），这样可以在 $O(\log \text{deg})$ 内查找或新建边；
• 下标列表：所有"恰好等于该节点所代表序列"的下标 $i$。

对每个 $i=1,\dots,N$，令 pos[i] 为 $A_i$ 所在的节点。由构造，$A_i = A_{x_i} + [y_i]$，所以只需看 pos[x_i] 的孩子中是否已有键 $y_i$：有则复用该节点，否则新建节点，然后令 pos[i] 为该子节点，并把 $i$ 追加进该节点的下标列表。

排序即 DFS：字典序排序等价于对这棵 Trie 做一次"先序"遍历，规则是：

1. 访问到某个节点时，先把该节点下标列表里的下标按升序输出。原因：该节点代表的序列是它所有后代节点所代表序列的前缀，而字典序中前缀更短者更小（$|S|<|T|$ 且 $S$ 是 $T$ 的前缀 $\Rightarrow S<T$）。
2. 然后按孩子边的值从小到大依次递归访问孩子。原因：两个序列的第一个不同位置恰好发生在它们共同前缀之后的分叉处，分叉处边上的值就是这个位置上的数，数值小者字典序小。

三条性质合起来就保证了 DFS 输出顺序正是题目要求的排列：

• 相等序列 $\to$ 同一节点 $\to$ 按下标升序输出；
• 前缀关系 $\to$ 先输出祖先节点；
• 分叉关系 $\to$ 按边值升序访问子树。

实现注意：Trie 深度最坏可达 $N=3\times 10^5$（链状），递归 DFS 有栈溢出风险，C++ 中建议用显式栈的迭代写法（本参考代码即如此）。总节点数至多 $N+1$，空间 $O(N)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<map<int, int>> nxt(1);   // 节点 0 为根，nxt[v][y] = 子节点编号
    vector<vector<int>> idx(1);     // 恰好等于该节点路径序列的下标列表
    vector<int> pos(n + 1, 0);      // pos[i]: A_i 所在节点

    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        if (!nxt[pos[x]].count(y)) {            // 没有该孩子则新建节点
            nxt[pos[x]][y] = (int)nxt.size();
            nxt.emplace_back();
            idx.emplace_back();
        }
        pos[i] = nxt[pos[x]][y];
        idx[pos[i]].push_back(i);               // idx 天然按下标升序
    }

    vector<int> ans;
    stack<int> st;
    st.push(0);
    while (!st.empty()) {
        int v = st.top();
        st.pop();

        for (int i : idx[v]) ans.push_back(i);  // 先输出当前节点的下标

        // 孩子按边值升序访问：把 map 中(键,值)按键逆序压栈
        vector<pair<int, int>> ch(nxt[v].begin(), nxt[v].end());
        for (auto it = ch.rbegin(); it != ch.rend(); ++it) {
            st.push(it->second);
        }
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

官方题解给出的 Python 写法（整理为迭代版本，避免递归深度问题）：

import sys

n = int(input())
nxt = [{}]        # 孩子表: 边值 -> 节点
idx = [[]]        # 各节点上的下标列表
pos = [0] * (n + 1)

for i in range(1, n + 1):
    x, y = map(int, input().split())
    if y not in nxt[pos[x]]:
        nxt[pos[x]][y] = len(nxt)
        nxt.append({})
        idx.append([])
    pos[i] = nxt[pos[x]][y]
    idx[pos[i]].append(i)

ans = []
stack = [0]
while stack:
    v = stack.pop()
    ans.extend(idx[v])
    for c in sorted(nxt[v].keys(), reverse=True):
        stack.append(nxt[v][c])

print(*ans)

复杂度分析

• 时间复杂度：$O(N \log N)$（map 的操作带来 $\log$ 因子；总节点数与总边数均为 $O(N)$）
• 空间复杂度：$O(N)$

---

F - Manhattan Christmas Tree 2

题目链接：https://atcoder.jp/contests/abc437/tasks/abc437_f

题目大意

二维平面上有 $N$ 棵圣诞树，第 $i$ 棵位于 $(X_i,Y_i)$。有 $Q$ 个操作：

• 1 i x y：把第 $i$ 棵树的坐标改为 $(x,y)$；
• 2 L R x y：输出点 $(x,y)$ 到区间 $[L,R]$ 内（按编号）所有树中曼哈顿距离的最大值。

曼哈顿距离定义为 $|x_1-x_2|+|y_1-y_2|$。

思路

这是曼哈顿距离问题的经典套路：旋转坐标系 45°。利用 $|a|=\max(a,-a)$，可以把曼哈顿距离展开再合并：

$$\begin{aligned} |x-X_i|+|y-Y_i| &= \max\{x-X_i,\ X_i-x\} + \max\{y-Y_i,\ Y_i-y\} \\ &= \max\left\{|(x+y)-(X_i+Y_i)|,\ |(x-y)-(X_i-Y_i)|\right\}. \end{aligned}$$

令 $U_i=X_i+Y_i$，$V_i=X_i-Y_i$，以及查询点的 $u=x+y$，$v=x-y$，则第 $i$ 棵树到查询点的曼哈顿距离为

$$d_i = \max\left\{|u-U_i|,\ |v-V_i|\right\}.$$

于是区间最大值可以拆开：

$$\max_{L\le i\le R} d_i = \max\left\{\max_{L\le i\le R}|u-U_i|,\ \max_{L\le i\le R}|v-V_i|\right\}.$$

而 $\max_i |u-U_i|$ 只可能在 $U_i$ 取区间极值时达到（离 $u$ 最近的"坐标值"必是区间内的最大值或最小值），即

$$\max_{L\le i\le R}|u-U_i| = \max\left\{|u-\min U_i|,\ |u-\max U_i|\right\}.$$

对 $V$ 同理。因此只需用线段树维护区间内 $U$ 的最小值/最大值与 $V$ 的最小值/最大值，共四棵线段树（或用两棵，每棵同时维护两个最值），支持单点修改与区间最值查询。

对每次类型 2 查询，取四个数中的最大值即可：

$$\text{ans}=\max\left\{|u-\min U|,\ |u-\max U|,\ |v-\min V|,\ |v-\max V|\right\}.$$

易错点：坐标范围 $\pm 10^9$，$U,V$ 以及距离的绝对值要用 long long 保存；修改时四棵线段树都要同步更新。

（官方题解使用了 AtCoder Library 的 segtree，下面给出不依赖任何外部库的迭代式线段树实现，效果相同。）

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Seg {                              // 迭代式线段树，维护区间 min 或 max
    int n;
    vector<long long> dat;
    bool mn;
    long long id;

    Seg(int sz, bool isMin) : mn(isMin) {
        id = isMin ? LLONG_MAX : LLONG_MIN;
        n = 1;
        while (n < sz) n <<= 1;
        dat.assign(2 * n, id);
    }

    long long merge(long long a, long long b) const {
        return mn ? min(a, b) : max(a, b);
    }

    void build(const vector<long long>& v) {
        for (int i = 0; i < (int)v.size(); i++) dat[n + i] = v[i];
        for (int i = n - 1; i >= 1; i--) dat[i] = merge(dat[i << 1], dat[i << 1 | 1]);
    }

    void set(int p, long long x) {
        p += n;
        dat[p] = x;
        for (p >>= 1; p; p >>= 1) dat[p] = merge(dat[p << 1], dat[p << 1 | 1]);
    }

    long long query(int l, int r) {       // 区间 [l, r)
        long long resl = id, resr = id;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, dat[l++]);
            if (r & 1) resr = merge(dat[--r], resr);
        }
        return merge(resl, resr);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> u(n), v(n);
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        u[i] = x + y;
        v[i] = x - y;
    }

    Seg uMin(n, true), uMax(n, false), vMin(n, true), vMax(n, false);
    uMin.build(u); uMax.build(u);
    vMin.build(v); vMax.build(v);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            long long x, y;
            cin >> i >> x >> y;
            i--;
            u[i] = x + y;
            v[i] = x - y;
            uMin.set(i, u[i]); uMax.set(i, u[i]);
            vMin.set(i, v[i]); vMax.set(i, v[i]);
        } else {
            int l, r;
            long long x, y;
            cin >> l >> r >> x >> y;
            l--;
            long long u0 = x + y, v0 = x - y;

            long long ans = 0;
            ans = max(ans, llabs(u0 - uMin.query(l, r)));
            ans = max(ans, llabs(u0 - uMax.query(l, r)));
            ans = max(ans, llabs(v0 - vMin.query(l, r)));
            ans = max(ans, llabs(v0 - vMax.query(l, r)));
            cout << ans << '\n';
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N + Q\log N)$
• 空间复杂度：$O(N)$

---

G - Colorful Christmas Tree

题目链接：https://atcoder.jp/contests/abc437/tasks/abc437_g

题目大意

一棵圣诞树有 $N$ 个灯泡（看作节点），由 $N-1$ 条丝带（看作边）连成一棵树。每个灯泡初始颜色为红（R）、绿（G）、蓝（B）之一。重复以下操作恰好 $N-1$ 次，目标是把所有丝带都剪掉：

1. 选一条尚未剪掉、且两端灯泡颜色不同的丝带剪掉；
2. 把剪掉的丝带两端灯泡的颜色各向后循环推进一格：红 $\to$ 绿 $\to$ 蓝 $\to$ 红。

判断是否可能剪掉全部丝带，若可能则输出任意一种合法的剪除顺序。共有 $T$ 组测试数据，满足 $\sum N^2 \le 2000^2$。

思路

这是一道思维量大、解法综合的压轴题，官方解法分两步：最大流判定可行性 + 贪心重构删除顺序。

先把三种颜色映射为 $0,1,2$（红、绿、蓝），并把"推进一格"视为对颜色加 $1$ 后对 $3$ 取模。

Step 1：固定每个顶点"以何颜色被删几次"。

对于顶点 $v$，其相邻的 $\deg(v)$ 条边最终都会被剪掉。每当剪掉 $v$ 的一条相邻边时，$v$ 的颜色就推进一格。因此 $v$ 在历次"被删"瞬间的颜色依次为

$$c_v,\ c_v+1,\ c_v+2,\ \dots,\ c_v+\deg(v)-1 \pmod 3,$$

这个多重集是固定的，与操作顺序无关。设 $A_{v,k}$ 为其中颜色 $k$ 出现的次数，则 $v$ 的所有相邻边中，恰有 $A_{v,k}$ 条必须在 $v$ 的颜色为 $k$ 时被剪掉。

Step 2：二分图最大流建模。

树是二分图，把顶点分为左、右两侧。构造网络：

• 源点 $S$、汇点 $T$，另外每个 $(v,k)$（$1\le v\le N$，$k=0,1,2$）是一个节点；
• 对每个左侧顶点 $u$、颜色 $k$：加边 $S\to (u,k)$，容量 $A_{u,k}$；
• 对每个右侧顶点 $v$、颜色 $k$：加边 $(v,k)\to T$，容量 $A_{v,k}$；
• 对每条树边（左端 $u$，右端 $v$）以及每一对 $k_1\ne k_2$：加边 $(u,k_1)\to (v,k_2)$，容量 $1$。

每条从 $S$ 到 $T$ 的单位流对应一条指派："树边 $(u,v)$ 在左端颜色为 $k_1$、右端颜色为 $k_2$ 时被剪掉"。注意 $k_1\ne k_2$ 正是操作要求"两端颜色不同"。

• 必要性：任何一个合法的剪除顺序都会自然产生 $N-1$ 条这样的指派（每条边被剪时两端颜色已定），并且每个顶点 $v$ 以颜色 $k$ 被剪的次数恰好是 $A_{v,k}$。这 $N-1$ 条指派正好构成一个值为 $N-1$ 的可行流。由于 $S$ 侧总容量 $=\sum_{\text{左 }u}\deg(u)=N-1$，故最大流的上界就是 $N-1$。
• 充分性：若最大流恰为 $N-1$，则 $S$、$T$ 侧的所有容量边都被饱和，且可以证明每条树边恰好获得一条指派：反复"剥叶子"——叶子的度数为 $1$，其唯一一条 $S$（或 $T$）侧容量边容量为 $1$ 且被饱和，故流必须全部经过它唯一相邻的那条树边，于是那条边恰有 $1$ 单位流；删去叶子后递归即得。于是我们得到 $N-1$ 条规则，每条规则形如"当 $u$ 的颜色为 $x$ 且 $v$ 的颜色为 $y$ 时，剪掉边 $(u,v)$"。

Step 3：由规则集贪心构造删除顺序。

下面这个引理保证了每一步都能找到一条"现在就可以执行"的规则：考虑当前剩余的树与剩余的规则。取一棵当前树的叶子 $v$ 与其父节点 $p$。因为 $\deg(v)=1$，$v$ 只剩一条相邻边，它在这条边被剪时必须处于当前颜色 $c_v$。若规则"$(v,p)$ 在 $v$ 色 $c_v$、$p$ 色 $x$ 时剪"当前不可执行，则必有 $x\ne c_p$。同理，$p$ 到其余每个孩子的边的规则中 $p$ 侧颜色也都不等于 $c_p$（否则那条边现在就符合条件，矛盾于"没有可执行的规则"）。但 $p$ 必须至少有某条边在它颜色为 $c_p$ 时被剪（因为 $A_{p,c_p}\ge 1$），这条边不可能是到孩子的边，只能是到父节点的边；于是"$(p,\text{父}(p))$ 的规则中父侧颜色 $\ne c_{\text{父}(p)}$"。沿根的方向一路推进，最终在根处矛盾：根没有父节点，但它必须有一条边在颜色 $c_{\text{根}}$ 时被剪，而它的所有孩子边都不可能满足。故反证成立：只要还有剩余规则，就至少存在一条可立即执行的规则。

剪掉一条规则后，把两端颜色各推进一格、删去该规则，剩余规则与剩余树依然满足同样的结构（每个顶点剩余的颜色多重集恰好是"当前颜色起连续 $\deg_{\text{剩余}}$ 个颜色"），于是可以归纳地继续执行。

重构实现：直接反复扫描规则列表，找出第一条两端颜色都匹配当前颜色的规则，执行它并删掉该规则。每次扫描 $O(N)$，共执行 $N-1$ 次，总代价 $O(N^2)$，满足 $\sum N^2\le 2000^2$ 的约束。

算法流程小结：求二分图染色 $\to$ 计算 $A_{v,k}$ $\to$ 建流并求最大流，若 $<N-1$ 输出 No $\to$ 否则从流中读出规则集，用上述贪心重构出顺序并输出。

参考代码

#include <bits/stdc++.h>
using namespace std;

// Dinic 最大流
struct Dinic {
    struct Edge { int to, rev; long long cap; };
    int n;
    vector<vector<Edge>> g;
    vector<int> level, it;

    Dinic(int n) : n(n), g(n), level(n), it(n) {}

    void add_edge(int from, int to, long long cap) {
        g[from].push_back({to, (int)g[to].size(), cap});
        g[to].push_back({from, (int)g[from].size() - 1, 0});
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto &e : g[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int &i = it[v]; i < (int)g[v].size(); i++) {
            Edge &e = g[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            long long f;
            while ((f = dfs(s, t, LLONG_MAX)) > 0) flow += f;
        }
        return flow;
    }

    // 返回正向边 (from,to) 上的流量（等于其反向边当前的容量）
    long long flow_of(int from, int to) {
        for (auto &e : g[to]) {
            if (e.to == from) return e.cap;
        }
        return 0;
    }
};

void solve() {
    int n;
    cin >> n;
    string cs;
    cin >> cs;
    vector<int> c(n);
    for (int i = 0; i < n; i++) c[i] = (cs[i] == 'R' ? 0 : cs[i] == 'G' ? 1 : 2);

    vector<pair<int, int>> edges(n - 1);
    vector<vector<int>> g(n);
    map<pair<int, int>, int> eid;          // 无向边 -> 编号
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges[i] = {a, b};
        eid[{a, b}] = eid[{b, a}] = i;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // 二分图染色：part = 0 左，1 右
    vector<int> part(n, -1);
    queue<int> q;
    part[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v]) {
            if (part[to] == -1) {
                part[to] = part[v] ^ 1;
                q.push(to);
            }
        }
    }

    // A[v][k]: 顶点 v 以颜色 k 被剪的次数（固定不变）
    vector<array<int, 3>> A(n);
    for (int v = 0; v < n; v++) {
        int cur = c[v];
        for (int i = 0; i < (int)g[v].size(); i++) {
            A[v][cur]++;
            cur = (cur + 1) % 3;
        }
    }

    int S = 3 * n, T = 3 * n + 1;
    Dinic din(3 * n + 2);
    vector<pair<int, int>> treepairs;      // 记录的树边颜色对边（用于读回流量）

    for (int v = 0; v < n; v++) {
        for (int k = 0; k < 3; k++) {
            if (A[v][k] == 0) continue;
            if (part[v] == 0) din.add_edge(S, 3 * v + k, A[v][k]);
            else din.add_edge(3 * v + k, T, A[v][k]);
        }
    }
    for (int i = 0; i < n - 1; i++) {
        int u = edges[i].first, v = edges[i].second;
        if (part[u] != 0) swap(u, v);     // 保证 u 在左、v 在右
        for (int k1 = 0; k1 < 3; k1++) {
            for (int k2 = 0; k2 < 3; k2++) {
                if (k1 == k2) continue;   // 两端颜色必须不同
                din.add_edge(3 * u + k1, 3 * v + k2, 1);
                treepairs.push_back({3 * u + k1, 3 * v + k2});
            }
        }
    }

    if (din.max_flow(S, T) != (long long)(n - 1)) {
        cout << "No\n";
        return;
    }

    // 读回规则：(u 的当前颜色为 x 时, v 的当前颜色为 y 时) 剪掉边 (u,v)
    vector<tuple<int, int, int, int>> ops;
    for (auto [f, to] : treepairs) {
        if (din.flow_of(f, to) == 1) {
            int u = f / 3, cu = f % 3;
            int v = to / 3, cv = to % 3;
            ops.emplace_back(u, cu, v, cv);
        }
    }

    // 贪心重构：每次找一条两端颜色都匹配当前颜色的规则
    vector<int> ans;
    while (!ops.empty()) {
        bool found = false;
        for (auto it = ops.begin(); it != ops.end(); ++it) {
            auto [u, cu, v, cv] = *it;
            if (c[u] == cu && c[v] == cv) {
                ans.push_back(eid[{u, v}]);
                ops.erase(it);
                c[u] = (c[u] + 1) % 3;
                c[v] = (c[v] + 1) % 3;
                found = true;
                break;
            }
        }
        if (!found) break;   // 依定理不会发生
    }

    cout << "Yes\n";
    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i] + 1;
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

官方题解给出的 Python 实现（依赖 AtCoder Library，atcoder.maxflow 提供 MFGraph）：

from atcoder.maxflow import MFGraph


def solve():
    n = int(input())
    c = [0 if i == "R" else 1 if i == "G" else 2 for i in input()]
    edge_id = {}
    G = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        edge_id[(a, b)] = edge_id[(b, a)] = i
        G[a].append(b)
        G[b].append(a)

    bipartite = [-1] * n
    bipartite[0] = 0
    mf = MFGraph(3 * n + 2)
    S = 3 * n
    T = S + 1

    stc = [0]
    while stc:
        v = stc.pop()
        cnt = [0] * 3
        tmp = c[v]
        for i in range(len(G[v])):
            cnt[tmp] += 1
            tmp = (tmp + 1) % 3

        for i in range(3):
            if bipartite[v] == 0:
                mf.add_edge(S, 3 * v + i, cnt[i])
            else:
                mf.add_edge(3 * v + i, T, cnt[i])

        if bipartite[v] == 0:
            for u in G[v]:
                for i in range(3):
                    for j in range(3):
                        if i != j:
                            mf.add_edge(3 * v + i, 3 * u + j, 1)

        for u in G[v]:
            if bipartite[u] == -1:
                bipartite[u] = bipartite[v] ^ 1
                stc.append(u)

    f = mf.flow(S, T)
    if f != n - 1:
        print("No")
        return

    op = []
    for e in mf.edges():
        if e.flow == 1 and 0 <= e.src < 3 * n and 0 <= e.dst < 3 * n:
            u, x = e.src // 3, e.src % 3
            v, y = e.dst // 3, e.dst % 3
            op.append((u, x, v, y))

    ans = []
    while op:
        for u, x, v, y in op:
            if c[u] == x and c[v] == y:
                op.remove((u, x, v, y))
                ans.append(edge_id[(u, v)])
                c[u] = (c[u] + 1) % 3
                c[v] = (c[v] + 1) % 3
                break

    print("Yes")
    print(*[i + 1 for i in ans])


for _ in range(int(input())):
    solve()

复杂度分析

• 时间复杂度：$O(N^2)$（单组测试；最大流在图规模 $O(N)$、流量上界 $N-1$ 下运行很快，贪心重构为 $O(N^2)$）。题目保证 $\sum N^2 \le 2000^2$，总复杂度在限制内。
• 空间复杂度：$O(N)$（存储图、流网络与规则集）