AtCoder Beginner Contest 453 题解

项目	内容
比赛时间	2026-04-11
比赛链接	https://atcoder.jp/contests/abc453
题目数量	A–G 共 7 题

比赛概览

本场 A 到 G 难度跨度较大：A、B 是热身题（字符串处理与简单模拟），C 是经典的 $2^N$ 枚举题，D 需要把"当前格子 + 上次移动方向"建模成状态图做 BFS，E 是一道值得掌握的计数题（按 A 队人数 $i$ 扫描，在 $O(N)$ 内维护四类人数并累加组合数），F 是一道较难的树上构造题（以"叶心"为枢纽构造合法染色），G 是典型的可持久化线段树应用。总体而言，D、E 是本场的分水岭，F、G 的构造与数据结构技巧值得重点掌握。

---

A - Trimo

题目链接：https://atcoder.jp/contests/abc453/tasks/abc453_a

题目大意

给定长度为 $N$（$1\le N\le 50$）的由小写字母组成的字符串 $S$，删除开头的所有连续字符 o，输出剩下的部分；若 $S$ 全是 o，则输出一个空行。

思路

直接模拟即可：从头扫描，找到第一个不是 o 的位置 $p$，输出 $S[p..N-1]$；若整个串都是 o（即不存在这样的 $p$），则输出空行。

另一种等价写法是用一个布尔标记 flag 表示"是否已经扫过第一个非 o 字符"：遇到 o 且 flag 已置位时才输出，遇到第一个非 o 字符时置位并输出。两种写法本质相同，关键是只删除开头的连续 o，中间的 o 必须保留（如样例 2 的 abcooo 完全不动）。

易错点：

• 输出"空字符串"指的是输出一个空行，即 cout << "\n"。
• 判断标准是字符 o 而非任意元音，不要看错。

参考代码

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

int main() {
    int N;
    string S;
    cin >> N >> S;

    size_t p = S.find_first_not_of('o');
    if (p == string::npos) {
        cout << "\n";              // 全部是 o，输出空行
    } else {
        cout << S.substr(p) << "\n";
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$（存储字符串）

---

B - Sensor Data Logging

题目链接：https://atcoder.jp/contests/abc453/tasks/abc453_b

题目大意

时间 $0,1,\dots,T$（$1\le T\le 100$）分别有读数 $A_i$。时间 $0$ 的读数必然被保存；对 $i=1,\dots,T$，当且仅当 $A_i$ 与最近一次保存的读数的差的绝对值至少为 $X$ 时，$A_i$ 才会被保存。按时间升序输出每次保存的时间与读数。

思路

直接按题意模拟。维护"最近一次保存的读数" $last$，初始 $last=A_0$，先输出 0 A_0；随后对每个 $i=1,\dots,T$：

• 计算差值 $d=|A_i-last|$；
• 若 $d\ge X$，更新 $last=A_i$ 并输出 i A_i；否则什么都不做。

关键点在于"最近一次保存的读数"：未保存的读数不会影响后续判断，比较对象始终是最近一次保存的那一个，而不是相邻时间戳的读数。求绝对值用 abs 函数即可（等价于 $|a-b|=\max(a,b)-\min(a,b)$）。

参考代码

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

int main() {
    int T, X;
    cin >> T >> X;

    int last;
    cin >> last;                    // A_0 必然保存
    cout << "0 " << last << "\n";

    for (int i = 1; i <= T; i++) {
        int a;
        cin >> a;
        if (abs(a - last) >= X) {   // 与最近一次保存的读数比较
            last = a;
            cout << i << " " << a << "\n";
        }
    }
    return 0;
}

复杂度分析

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

---

C - Sneaking Glances

题目链接：https://atcoder.jp/contests/abc453/tasks/abc453_c

题目大意

高桥君一开始位于数轴上的 $0.5$ 处。他要进行 $N$ 次移动（$1\le N\le 20$），第 $i$ 次可以任选正方向或负方向移动距离 $L_i$（$1\le L_i\le 10^9$）。问最多能经过坐标 $0$ 多少次？（题目保证任何一次移动结束后都不会恰好停在 $0$ 上。）

思路

关键观察：每次移动方向是一个二元选择（正/负），而 $N\le 20$ 很小，可以直接 $2^N$ 枚举所有方向组合，对每个组合模拟整条路径并统计经过 $0$ 的次数。

用整数避免小数：直接模拟会涉及起点 $0.5$ 这个小数，处理起来不便。把所有坐标整体放大 2 倍：起点变为 $1$，第 $i$ 次移动距离变为 $2L_i$。由于每次移动的距离都是偶数，所以任意时刻位置都是奇数，永远不可能恰好停在 $0$ 上，因此"经过 $0$"等价于"移动前后位置的符号相反"：

$$x\cdot x' < 0,$$

其中 $x$ 是移动前坐标，$x'$ 是移动后坐标。注意直接判断乘积可能溢出（放大两倍后坐标绝对值可达 $1+2\sum L_i\le 4\times 10^{10}$，超出 int 范围），应先把坐标压缩成符号函数 $\mathrm{sgn}(x)\in\{-1,0,1\}$，再判断

$$\mathrm{sgn}(x)\cdot\mathrm{sgn}(x')<0.$$

为什么贪心不对：直观上"每次都朝 0 的方向走"似乎最优，但这是错的。反例 $L=(40,50,90,1,1,1)$：贪心只能经过 3 次 $0$，而选择方向（负、负、正、负、正、负）：

$$0.5 \xrightarrow{-40} -39.5 \xrightarrow{-50} -89.5 \xrightarrow{+90} 0.5 \xrightarrow{-1} -0.5 \xrightarrow{+1} 0.5 \xrightarrow{-1} -0.5$$

能经过 $0$ 达 5 次。因此必须全面枚举。

复杂度：$2^N\times N$ 次判断，当 $N=20$ 时约为 $2\times 10^7$，在时限内绰绰有余。

参考代码

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

ll sgn(ll x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

int main() {
    int N;
    cin >> N;
    vector<ll> L(N);
    for (ll& x : L) cin >> x;

    ll best = 0;
    for (ll mask = 0; mask < (1LL << N); mask++) {
        ll pos = 1;                            // 起点 2*0.5 = 1
        ll cnt = 0;
        for (int j = 0; j < N; j++) {
            ll npos = (mask >> j & 1) ? pos + 2 * L[j] : pos - 2 * L[j];
            if (sgn(pos) * sgn(npos) < 0) cnt++;   // 符号变化即经过 0
            pos = npos;
        }
        best = max(best, cnt);
    }
    cout << best << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O(2^N N)$
• 空间复杂度：$O(N)$

---

D - Go Straight

题目链接：https://atcoder.jp/contests/abc453/tasks/abc453_d

题目大意

$H\times W$ 的网格（$1\le H,W\le 1000$），每个格子是六种字符之一：

• #：不可进入；
• .：可自由进入、自由离开（进出方向均无限制）；
• o：进入该格后必须沿进入方向继续前进（不许转向）；
• x：进入该格后不能沿进入方向前进（必须换一个方向）；
• S：起点，行为同 .；
• G：终点，行为同 .。

判断能否从 S 走到 G，若能则输出一条长度不超过 $5\times 10^6$ 的移动序列（由 U/D/L/R 组成）。

思路

关键观察：高桥君"下一步能怎么走"只取决于两件事——他当前在哪个格子，以及他上一次移动的方向；与他更早的历史完全无关。这是因为 o、x 的限制只涉及"进入当前格子的方向"。

于是把状态定义为二元组：

$$\text{state}=(\text{当前格子},\ \text{上次移动的方向}),$$

方向有 $\mathrm{U},\mathrm{D},\mathrm{L},\mathrm{R}$ 四种，总状态数 $4HW\le 4\times 10^6$。

设当前在格子 $(i,j)$，上次移动方向为 $d_1$（即是从哪个方向进入 $(i,j)$ 的），想朝方向 $d_2$ 离开，则转移条件为：

• 若 $S_{i,j}=\texttt{o}$：必须保持方向，仅当 $d_2=d_1$ 时允许；
• 若 $S_{i,j}=\texttt{x}$：必须转向，仅当 $d_2\ne d_1$ 时允许；
• 若 $S_{i,j}\in\{\texttt{.},\texttt{S},\texttt{G}\}$：两种方向都允许。

另外要求目标格 $(i,j)+\mathrm{dir}(d_2)$ 存在且不为 #。（# 格不可能成为状态，无需考虑。）

据此在图 $(V,E)$ 上求可达性：$V$ 是所有状态，从状态 $((i,j),d_1)$ 向 $(((i,j)+\mathrm{dir}(d_2)),d_2)$ 连有向边。起点集合为所有 $(\texttt{S},d)$（4 个状态），终点集合为所有 $(\texttt{G},d)$。从起点集合做多源 BFS 即可：

• 若某个 $(\texttt{G},d)$ 状态被访问到，说明可达，答案为 Yes；
• BFS 结束后仍未到达任何 $(\texttt{G},d)$，则答案为 No。

为什么状态数上限就保证了路径长度限制：BFS 中每个顶点至多被访问一次，所以 BFS 树深度 $\le 4HW-1<5\times 10^6$，每条树边恰对应一次移动，故恢复出的移动序列长度天然满足题目的 $5\times 10^6$ 上限。

路径恢复：记录每个状态第一次被访问时的前驱状态，以及进入该状态所用的方向字符；从某个到达的 $(\texttt{G},d)$ 状态沿前驱回溯到起点状态，将方向字符翻转即得答案。注意起点状态没有"上次移动方向"，把 $(\texttt{S},d)$ 四个状态都作为起点即可（S 本身无方向限制，起点带什么方向都不影响）。

实现时用编号 $(i\cdot W+j)\cdot 4+d$ 表示状态，$d\in\{0,1,2,3\}$ 对应 U/D/L/R。

参考代码

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

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

    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    int sx = -1, sy = -1, gx = -1, gy = -1;
    for (int i = 0; i < H; i++) {
        cin >> S[i];
        for (int j = 0; j < W; j++) {
            if (S[i][j] == 'S') { sx = i; sy = j; }
            if (S[i][j] == 'G') { gx = i; gy = j; }
        }
    }

    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};
    const char dc[4] = {'U', 'D', 'L', 'R'};

    int tot = H * W * 4;
    vector<int> prev(tot, -1);     // 前驱状态，-2 表示起点
    vector<char> dir(tot, '?');    // 进入该状态所用的方向字符

    auto id = [&](int i, int j, int d) { return (i * W + j) * 4 + d; };

    queue<int> q;
    for (int d = 0; d < 4; d++) {  // 起点无方向限制，四个方向状态都入队
        int s = id(sx, sy, d);
        prev[s] = -2;
        q.push(s);
    }

    int goal = -1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        int pos = cur / 4, i = pos / W, j = pos % W, d1 = cur % 4;
        for (int d2 = 0; d2 < 4; d2++) {
            if (S[i][j] == 'o' && d2 != d1) continue;  // o：必须保持方向
            if (S[i][j] == 'x' && d2 == d1) continue;  // x：必须转向
            int ni = i + dx[d2], nj = j + dy[d2];
            if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
            if (S[ni][nj] == '#') continue;
            int nxt = id(ni, nj, d2);
            if (prev[nxt] != -1) continue;             // 已访问
            prev[nxt] = cur;
            dir[nxt] = dc[d2];
            if (ni == gx && nj == gy) { goal = nxt; break; }
            q.push(nxt);
        }
        if (goal != -1) break;
    }

    if (goal == -1) {
        cout << "No\n";
        return 0;
    }

    string ans;
    int cur = goal;
    while (prev[cur] != -2) {
        ans += dir[cur];
        cur = prev[cur];
    }
    reverse(ans.begin(), ans.end());

    cout << "Yes\n" << ans << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O(HW)$（状态数 $4HW$，每个状态至多扩展 4 个方向）
• 空间复杂度：$O(HW)$（前驱与方向数组）

---

E - Team Division

题目链接：https://atcoder.jp/contests/abc453/tasks/abc453_e

题目大意

把 $N$ 名选手（$2\le N\le 2\times 10^5$）分入两支可区分的队伍 A、B，要求：

• 每队至少一人；
• 每人恰好属于一队；
• 选手 $i$ 所在队伍的人数在 $[L_i,R_i]$ 之间。

求满足条件的分配方案数，模 $998244353$。

思路

固定 A 队人数。由于两队人数互补，枚举 A 队人数 $i$（$1\le i\le N-1$），则 B 队人数 $j=N-i$。对每位选手 $k$，两个布尔量决定了它可去哪些队：

$$\text{aok}_k \iff L_k\le i\le R_k,\qquad \text{bok}_k \iff L_k\le N-i\le R_k.$$

据此把选手分成四类：

类别	$\text{aok}_k$	$\text{bok}_k$	含义
1	真	真	两队均可
2	真	假	只能进 A
3	假	真	只能进 B
4	假	假	两队都进不了

记 $c_{11},c_{10},c_{01},c_{00}$ 分别为类别 1、2、3、4 的人数。对固定的 $i$，方案存在的充要条件是：

• $c_{00}=0$（否则有人无处可去）；
• $c_{10}\le i$（A 队要装得下所有"只能进 A"的人）；
• $c_{01}\le N-i$（同理）。

满足条件时，"只能进 A"的人全部进 A，"只能进 B"的人全部进 B；A 队还缺 $i-c_{10}$ 人，从 $c_{11}$ 个"两队均可"的选手中任意选出即可，因此该 $i$ 的方案数为

$$\binom{c_{11}}{i-c_{10}}=\frac{c_{11}!}{(i-c_{10})!\,(N-i-c_{01})!}.$$

答案即对 $i=1,\dots,N-1$ 求和后取模。

如何 $O(N)$ 求出所有 $i$ 对应的四类人数？ 朴素做法是对每个 $i$ 扫描全部选手，总复杂度 $O(N^2)$。观察发现：随着 $i$ 递增，每位选手的状态只变化 4 次——"能进 A"在 $i=L_k$ 由假变真、在 $i=R_k+1$ 由真变假；"能进 B"在 $i=N-R_k$ 由假变真、在 $i=N-L_k+1$ 由真变假。于是用差分的思想：在数组 $\text{cand}[i]$ 中记录"当 $i$ 从 $i-1$ 变到 $i$ 时状态可能变化的选手"，每步只重新计算这些选手的 $\text{aok},\text{bok}$，把旧组人数减一、新组人数加一。总变化次数为 $4N$，故总体 $O(N)$。

组合数通过预处理 $0!,\dots,N!$ 及其模逆元做到 $O(1)$ 查询。

参考代码

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

const ll MOD = 998244353;

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

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

    int N;
    cin >> N;
    vector<int> L(N), R(N);
    vector<vector<int>> cand(N + 2);
    for (int i = 0; i < N; i++) {
        cin >> L[i] >> R[i];
        // 选手 i 状态变化的 4 个时刻
        cand[L[i]].push_back(i);          // aok 变真
        cand[R[i] + 1].push_back(i);      // aok 变假
        cand[N - R[i]].push_back(i);      // bok 变真
        cand[N - L[i] + 1].push_back(i);  // bok 变假
    }

    vector<ll> fact(N + 1), invfact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
    invfact[N] = modpow(fact[N], MOD - 2);
    for (int i = N; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;

    auto C = [&](int n, int k) -> ll {
        if (k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
    };

    vector<int> aok(N, 0), bok(N, 0);
    int m[2][2] = {};
    m[0][0] = N;   // i=0 时 L_k>=1 使 aok 为假、N-i=N>R_k 使 bok 为假，所有人都在第 4 类

    ll ans = 0;
    for (int i = 1; i <= N - 1; i++) {
        for (int z : cand[i]) {
            m[aok[z]][bok[z]]--;
            aok[z] = (L[z] <= i && i <= R[z]) ? 1 : 0;
            bok[z] = (L[z] <= N - i && N - i <= R[z]) ? 1 : 0;
            m[aok[z]][bok[z]]++;
        }
        if (m[0][0] == 0 && m[1][0] <= i && m[0][1] <= N - i) {
            ans = (ans + C(m[1][1], i - m[1][0])) % MOD;
        }
    }
    cout << ans << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O(N\log P)$，其中 $P=998244353$（预处理阶乘与逆元）；状态扫描与统计为 $O(N)$
• 空间复杂度：$O(N)$

---

F - Avoid Division

题目链接：https://atcoder.jp/contests/abc453/tasks/abc453_f

题目大意

给一棵 $N$ 个顶点（$2\le N\le 3\times 10^5$）的树，用 $K$ 种颜色给顶点染色，颜色 $i$ 最多使用 $C_i$ 次（保证 $\sum C_i\ge N$）。要求对每条边：砍掉这条边后得到的两个连通块，都存在某种颜色 $i$，使得两个块中各至少有一个顶点染了颜色 $i$。判断是否可行，可行则输出一种合法染色方案，否则输出 -1。共有 $T$ 组测试数据，$\sum N\le 3\times 10^5$。

思路

设 $L$ 为树的叶子（度数为 1 的顶点）个数。本题是一道较难的构造题。

特例 $N=2$：两顶点之间仅一条边，砍掉后两个连通块各只有一个顶点，因此需要某颜色 $i$ 满足 $C_i\ge 2$，把两个顶点都染成 $i$；否则无解。

一般情况 $N\ge 3$ 的判定：关键结论是

存在合法染色，当且仅当所有满足 $C_i\ge 2$ 的颜色容量之和至少为 $L$。

必要性：叶子只能染容量 $\ge 2$ 的颜色。若某片叶子染了容量为 1 的颜色 $c$，则砍掉它唯一的邻边后，含这片叶子的连通块只有它一个点，无法与另一个块共享颜色 $c$。而若容量之和小于 $L$，必然有叶子被迫使用容量为 1 的颜色，故无解。

下面构造充分性。

第一步：找"叶心" $X$。 找一个非叶顶点 $X$，使得删掉 $X$ 及其邻边后，每个连通分量至多包含 $L/2$ 片叶子（注意：删除后才变成叶子的顶点不计入）。可用一次后序 DFS 得到：取第一个满足"其子树至少含 $L/2$ 片叶子，且每个子分量叶子数 $\le L/2$"的顶点。当 $N\ge 3$ 时这样的顶点必然不是叶子，且删掉它后至少分成两个分量。

第二步：按分量分组。 把 $L$ 片叶子按"删掉 $X$ 后所属的连通分量"分组。分组数至少为 2，且每组叶子数 $\le L/2$。

第三步：给叶子染色。 依次处理每个 $C_i\ge 2$ 的颜色 $i$，用优先队列维护"当前未染叶子数最多的组"：

• 若只剩一片未染叶子：把它和 $X$ 都染成颜色 $i$，结束叶子染色；
• 若未染叶子总数 $\le C_i$：把所有剩余叶子全部染成颜色 $i$；
• 否则：从叶子数最多的组和次多的组各取一片染成 $i$，再反复从当前最多组取一片染成 $i$，直到用完 $C_i$ 次。

该贪心保持不变量：处理完每个颜色后，若还剩 $L'$ 片未染叶子、最大组有 $M'$ 片，则 $M'\le (L'+1)/2$。因此当 $L'\ge 2$ 时未染叶子至少分布在两个组中，"从两个不同组各取一片"始终可行，且最大组也始终有足够的叶子供后续取用。

第四步：染剩余顶点。 所有叶子染完后，把其余顶点（都不是叶子）用仍然有剩余容量的颜色任意染完。因为 $\sum C_i\ge N$，剩余容量一定足够。容量为 1 的颜色在此步使用正好安全（它们只会出现在非叶顶点上）。

为什么这样构造一定满足条件？ 考虑砍掉任一条边，把树分成不含 $X$ 的部分 $P$ 和含 $X$ 的部分 $Q$。$P$ 必含至少一片叶子 $Y$。由染色过程可知，叶子 $Y$ 的颜色与"另一组中的某片叶子"或与 $X$ 相同；而 $Q$ 恰好包含 $X$ 以及所有其他组的叶子，因此 $P$、$Q$ 共享 $Y$ 的颜色，条件成立。

若第三步结束后仍有未染叶子（等价于 $\sum_{C_i\ge 2}C_i<L$），则输出 -1。

实现要点：求 $X$ 时用后序遍历同时维护子树叶子数 $w[k]$；对 $X$ 的每个邻接子树收集其叶子；用 priority_queue<pair<未染数, 组号>> 维护各组状态。参考代码中这两处遍历均写成迭代形式，与递归写法完全等价，但即使在链式树（递归深度可达 $N$）上也无需担心爆栈。

参考代码

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

const int MAXN = 300005;
vector<int> g[MAXN];
int w[MAXN];
int ans[MAXN];
int C[MAXN];
int leafCnt, cent;

// 收集删掉 cent 后某分量内的所有叶子（迭代遍历，避免链式树递归爆栈）
void collectLeaves(int cent, int start, vector<int>& leaves) {
    stack<pair<int, int>> st;
    st.push({start, cent});
    while (!st.empty()) {
        auto [x, p] = st.top();
        st.pop();
        if ((int)g[x].size() == 1) leaves.push_back(x);
        for (int nx : g[x]) {
            if (nx == p) continue;
            st.push({nx, x});
        }
    }
}

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

    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        for (int i = 0; i < N; i++) g[i].clear();
        for (int i = 0; i < N - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--; v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for (int i = 0; i < K; i++) cin >> C[i];
        fill(ans, ans + N, -1);

        if (N == 2) {                // 特例：两顶点必须同色
            int col = -1;
            for (int i = 0; i < K; i++) if (C[i] >= 2) { col = i; break; }
            if (col == -1) cout << -1 << "\n";
            else cout << col + 1 << " " << col + 1 << "\n";
            continue;
        }

        leafCnt = 0;
        for (int i = 0; i < N; i++) if (g[i].size() == 1) leafCnt++;

        // 迭代后序遍历求叶心 X：子树至少含 leafCnt/2 片叶子，
        // 且各子分量叶子数 <= leafCnt/2（等价于官方递归写法，但链式树上不爆栈）
        vector<int> parent(N, -1), order;
        order.reserve(N);
        stack<pair<int, int>> st;
        st.push({0, -1});
        while (!st.empty()) {
            auto [k, p] = st.top();
            st.pop();
            parent[k] = p;
            order.push_back(k);
            for (int nx : g[k]) {
                if (nx == p) continue;
                st.push({nx, k});
            }
        }
        cent = -1;
        for (int idx = N - 1; idx >= 0; idx--) {   // 逆序即后序
            int k = order[idx];
            int sz = (int)g[k].size();
            w[k] = (sz == 1) ? 1 : 0;
            bool ok = true;
            for (int nx : g[k]) {
                if (nx == parent[k]) continue;
                w[k] += w[nx];
                int tmp = w[nx];
                if (sz == 1) tmp++;          // 排除叶子作为 X
                if (tmp * 2 > leafCnt) ok = false;
            }
            if (ok && leafCnt <= w[k] * 2) cent = k;
        }

        // 删掉 X 后按分量收集叶子
        vector<vector<int>> groups;
        for (int nx : g[cent]) {
            vector<int> leaves;
            collectLeaves(cent, nx, leaves);
            groups.push_back(leaves);
        }

        priority_queue<pair<int, int>> pq;   // (未染叶子数, 组号)
        for (int i = 0; i < (int)groups.size(); i++)
            pq.push({(int)groups[i].size(), i});

        int rem = leafCnt;                   // 未染叶子总数
        for (int i = 0; i < K && rem > 0; i++) {
            if (C[i] <= 1) continue;
            if (rem == 1) {                  // 只剩一片叶子：与 X 同色收尾
                auto pr = pq.top(); pq.pop();
                ans[groups[pr.second][pr.first - 1]] = i;
                ans[cent] = i;
                C[i] -= 2;
                rem = 0;
            } else if (rem <= C[i]) {        // 容量足够：剩余叶子全部染 i
                while (!pq.empty()) {
                    auto pr = pq.top(); pq.pop();
                    for (int j = 0; j < pr.first; j++) ans[groups[pr.second][j]] = i;
                    C[i] -= pr.first;
                    rem -= pr.first;
                }
            } else {                          // 两组各取一片 + 从最大组继续
                auto pr = pq.top(); pq.pop();
                auto ps = pq.top(); pq.pop();
                ans[groups[pr.second][pr.first - 1]] = i;
                ans[groups[ps.second][ps.first - 1]] = i;
                if (pr.first > 1) pq.push({pr.first - 1, pr.second});
                if (ps.first > 1) pq.push({ps.first - 1, ps.second});
                C[i] -= 2;
                rem -= 2;
                for (int j = 0; j < C[i]; j++) {
                    auto t = pq.top(); pq.pop();
                    ans[groups[t.second][t.first - 1]] = i;
                    if (t.first > 1) pq.push({t.first - 1, t.second});
                    rem--;
                }
                C[i] = 0;
            }
        }

        if (rem > 0) {                       // 叶子没染完：无解
            cout << -1 << "\n";
            continue;
        }

        int cur = 0;                         // 剩余顶点用剩余容量染色
        for (int i = 0; i < N; i++) {
            if (ans[i] < 0) {
                while (cur < K && C[cur] <= 0) cur++;
                ans[i] = cur;
                C[cur]--;
            }
        }
        for (int i = 0; i < N; i++) {
            if (i) cout << " ";
            cout << ans[i] + 1;
        }
        cout << "\n";
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N\log N)$（求 $X$ 的 DFS 为 $O(N)$；叶子染色用优先队列，每次染色 $O(\log N)$，总操作 $O(N\log N)$）
• 空间复杂度：$O(N)$

---

G - Copy Query

题目链接：https://atcoder.jp/contests/abc453/tasks/abc453_g

题目大意

有 $N$ 个长度均为 $M$ 的序列 $A_1,\dots,A_N$，初值全为 0（$N,M\le 2\times 10^5$）。依次处理 $Q\le 2\times 10^5$ 个询问，共三种类型：

• 类型 1：把序列 $A_X$ 整体覆盖为序列 $A_Y$；
• 类型 2：把 $A_X$ 的第 $Y$ 个元素改为 $Z$；
• 类型 3：输出 $\sum_{j=L}^{R}A_{X,j}$。

思路

类型 1 要求"把整条序列复制过去"，若用普通线段树直接复制需要 $O(M)$，不可接受。但注意：复制之后 $A_X$ 与 $A_Y$ 共享一份数据，而后续对其中之一的单点修改不能影响另一个——这正是**可持久化线段树（persistent segment tree）**解决的问题：它允许在某个历史版本上做单点更新并生成新版本，同时旧版本保持不变。

做法：不为每个序列存整个数组，而是为每个序列 $A_i$ 维护一个线段树的根结点指针 $root_i$。初始所有 $root_i$ 指向一棵全 0 的树。

• 类型 1：直接让 root[X] = root[Y]，$O(1)$。两个序列从此指向同一个版本。
• 类型 2：对 $root[X]$ 做可持久化单点更新，得到一棵新树作为 root[X]，$O(\log M)$。更新时只把根到该叶子路径上 $O(\log M)$ 个结点克隆出来再修改，旧树（可能仍被其他序列共享）完全不受影响。
• 类型 3：对 $root[X]$ 做区间和查询，$O(\log M)$。

为什么可持久化线段树能做到：线段树的单点更新只会改动根到叶子的一条链（$O(\log M)$ 个结点），其余结点原样复用。可持久化版本的做法就是"按需克隆"：把要改的结点复制一份再改，让新版本的指针指向克隆出的新结点，旧结点不动。这样每个历史版本都由其唯一的根标识，且每个版本都可以独立查询、独立更新。类型 1 只是让两个根指向同一版本；之后任一序列做类型 2 时克隆出新版本，两者互不干扰。

实现细节：结点可以动态分配，也可以用三个数组（左儿子、右儿子、和）加一个结点计数器来模拟"地址"。初始建树 $2M-1$ 个结点，每个类型 2 新建 $O(\log M)$ 个结点，总结点数约 $O(M+Q\log M)$。递归深度仅 $O(\log M)$。

参考代码

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

// 可持久化线段树：用数组存储结点，结点编号即"地址"
vector<int> lc, rc;
vector<ll> sum;

int newNode() {
    lc.push_back(0);
    rc.push_back(0);
    sum.push_back(0);
    return (int)lc.size() - 1;
}

int build(int l, int r) {                // 建全 0 线段树
    int id = newNode();
    if (l + 1 == r) return id;
    int m = (l + r) / 2;
    lc[id] = build(l, m);
    rc[id] = build(m, r);
    return id;
}

int setval(int t, int l, int r, int pos, ll v) {   // 可持久化单点赋值
    int id = newNode();
    lc[id] = lc[t];
    rc[id] = rc[t];
    if (l + 1 == r) {
        sum[id] = v;
        return id;
    }
    int m = (l + r) / 2;
    if (pos < m) lc[id] = setval(lc[t], l, m, pos, v);
    else rc[id] = setval(rc[t], m, r, pos, v);
    sum[id] = sum[lc[id]] + sum[rc[id]];
    return id;
}

ll query(int t, int l, int r, int ql, int qr) {    // 区间和
    if (qr <= l || r <= ql) return 0;
    if (ql <= l && r <= qr) return sum[t];
    int m = (l + r) / 2;
    return query(lc[t], l, m, ql, qr) + query(rc[t], m, r, ql, qr);
}

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

    int N, M, Q;
    cin >> N >> M >> Q;

    int zero = build(0, M);              // 全 0 的初始版本
    vector<int> root(N, zero);           // root[i] 表示序列 A_i 的版本

    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {                    // A_X := A_Y
            int x, y;
            cin >> x >> y;
            x--; y--;
            root[x] = root[y];
        } else if (t == 2) {             // A_X[Y] := Z
            int x, y, z;
            cin >> x >> y >> z;
            x--; y--;
            root[x] = setval(root[x], 0, M, y, z);
        } else {                         // 输出区间和
            int x, l, r;
            cin >> x >> l >> r;
            x--; l--;
            cout << query(root[x], 0, M, l, r) << "\n";
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：类型 1 为 $O(1)$，类型 2、类型 3 均为 $O(\log M)$
• 空间复杂度：$O(M+Q\log M)$（可持久化线段树的结点总数）