AtCoder Beginner Contest 460 题解

for-each2026年8月18日大约 23 分钟

AtCoder Beginner Contest 460 题解

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

比赛概览

本场难度分布较为均衡：A、B 为签到题与简单几何题；C 是经典贪心 + 双指针；D 考察对同步元胞自动机的观察，核心是把问题化成"一次操作后的多源 BFS 距离的奇偶性"；E 是较直白的数论分类讨论。后半场明显上强度：F 需要"集合直径可以用端点合并"的引理配合线段树，是区分度较高的一题；G 需要在树上动态维护换根 DP（静态 top tree 或 HLD），是全场最难。建议重点掌握 D、F、G 的思想。

A - Mod While Positive

题目链接：https://atcoder.jp/contests/abc460/tasks/abc460_a

题目大意

给定正整数 $N, M$ 。当 $M$ 不为 $0$ 时，重复执行以下操作：令 $x$ 为 $N$ 除以 $M$ 的余数，把 $M$ 替换为 $x$ 。求操作的执行次数。题目保证有限次后 $M$ 会变为 $0$ 。

思路

直接按题意模拟即可：

while (M > 0) {
    M = N % M;
    ans++;
}

关键在于理解"为什么一定会结束"。当 $M > 0$ 时，余数 $N \bmod M$ 一定落在 $[0, M-1]$ 内，即新值严格小于旧值 $M$ 。因此每做一次操作 $M$ 就严格变小，最多经过初始 $M$ 次操作后 $M$ 必然变成 $0$ 。所以 while 循环必然终止，且迭代次数不超过初始的 $M$ 。

注意 $N$ 与 $M$ 的角色：这里 $N$ 始终不变，只有 $M$ 在变，所以它并不是欧几里得算法（欧几里得算法每次会交换两个数的角色），只是"用固定的 $N$ 反复取模"。

参考代码

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

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

    int n, m;
    cin >> n >> m;
    int ans = 0;
    while (m > 0) {
        m = n % m;
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(M)$ （迭代次数不超过初始 $M \le 1000$ ）
空间复杂度： $O(1)$

B - Two Rings

题目链接：https://atcoder.jp/contests/abc460/tasks/abc460_b

题目大意

在 $xy$ 平面上有两个圆 $C_1, C_2$ （本题中的"圆"指的是圆周，不含内部）。 $C_1$ 圆心 $(X_1,Y_1)$ 、半径 $R_1$ ， $C_2$ 圆心 $(X_2,Y_2)$ 、半径 $R_2$ 。判断两个圆周是否有公共点。共有 $T$ 组询问。

思路

设两圆心之间的距离为 $D$ 。两个圆周有公共点当且仅当两圆"外离"或"小圆完全在大圆内部且不相切"这两种情形不出现，即

|R_1 - R_2| \le D \le R_1 + R_2.

直观理解：若 $D > R_1 + R_2$ ，两圆外离，圆周不相交；若 $D < |R_1 - R_2|$ ，小圆完全藏在大圆内部，圆周不相交；等号对应外切/内切，恰好有一个公共点。

其中

D = \sqrt{(X_1-X_2)^2 + (Y_1-Y_2)^2}.

精度问题（本题的关键陷阱）：直接开根号计算 $D$ 可能因浮点误差而判错。注意到不等式的两边都是非负数，因此对两边同时平方不会改变不等式的真假，从而可以完全用整数运算：

(R_1-R_2)^2 \le (X_1-X_2)^2 + (Y_1-Y_2)^2 \le (R_1+R_2)^2.

坐标与半径最大为 $10^9$ ，平方后最大约 $4 \times 10^{18}$ ，仍在 long long（约 $9.2 \times 10^{18}$ ）范围内，故使用 long long 即可。

参考代码

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

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

    int T;
    cin >> T;
    while (T--) {
        long long x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
        auto sq = [](long long x) { return x * x; };
        long long L = sq(r1 - r2);
        long long M = sq(x1 - x2) + sq(y1 - y2);
        long long R = sq(r1 + r2);
        cout << (L <= M && M <= R ? "Yes" : "No") << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：每组 $O(1)$ ，共 $O(T)$
空间复杂度： $O(1)$

C - Sushi

题目链接：https://atcoder.jp/contests/abc460/tasks/abc460_c

题目大意

有 $N$ 份醋饭（shari），第 $i$ 份重量为 $A_i$ ；有 $M$ 份配料（neta），第 $j$ 份重量为 $B_j$ 。做一份寿司需要一份醋饭配一份配料，要求配料的重量不超过醋饭重量的两倍（ $B \le 2A$ ），每份食材最多用一次。求最多能做出多少份寿司。

思路

把问题看成二分图匹配的计数问题，但我们不需要一般匹配算法，因为约束 $B \le 2A$ 具有很好的单调性。

关键观察：可以假设"小醋饭配小配料"。 先把配料升序排好 $b_1 \le b_2 \le \cdots$ ，再考虑所用醋饭 $a_1, a_2, \ldots$ （ $a_i$ 配 $b_i$ ）。若存在 $a_i > a_{i+1}$ ，由两个配对都合法可知

2a_i \ge b_i, \qquad 2a_{i+1} \ge b_{i+1}.

因为 $b_i \le b_{i+1}$ ，所以 $2a_{i+1} \ge b_{i+1} \ge b_i$ ，即交换后 $a_{i+1}$ 仍配得上 $b_i$ ；又 $a_i > a_{i+1}$ 推出 $2a_i \ge 2a_{i+1} \ge b_{i+1}$ ，即 $a_i$ 也配得上 $b_{i+1}$ 。于是把 $a_i, a_{i+1}$ 交换，两个配对依然合法。反复交换，就可以把所用醋饭也排成升序，且不损失任何配对。

贪心算法。 将 $A, B$ 都升序排序，用双指针扫一遍：

指针 $i$ 指向当前可用的最小醋饭；
对于每个配料 $b_j$ ，先把所有 $2A_i < b_j$ 的醋饭丢弃（它们连当前配料都配不上，而后面配料更大，更配不上）；
若还有剩余醋饭，就把最前面的那份 $A_i$ （满足 $2A_i \ge b_j$ ）与 $b_j$ 配对， $i$ 后移。

为什么这是最优的：面对当前（最小）的配料 $b_j$ ，任何方案都必须给它找一个 $2A \ge b_j$ 的醋饭；选其中最小的一份是安全的——把更大的醋饭留给后面更大的配料只会更好。交换论证保证了排序后贪心的正确性。

易错点： $A_i$ 最大 $10^9$ ， $2A_i$ 用 long long 计算更稳妥。

参考代码

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

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

    int n, m;
    cin >> n >> m;
    vector<long long> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int x = 0, ans = 0;
    for (int i = 0; i < m; i++) {
        while (x < n && a[x] * 2 < b[i]) x++;  // 丢掉配不上的醋饭
        if (x < n) {                            // 取最小可用醋饭配对
            x++;
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N + M \log M)$ （瓶颈是排序）
空间复杂度： $O(N + M)$

D - Repeatedly Repainting

题目链接：https://atcoder.jp/contests/abc460/tasks/abc460_d

题目大意

有一个 $H \times W$ 的网格，每格为白或黑。执行 $10^{100}$ 次如下同步操作：一个操作前为白的格子，当且仅当它存在至少一个黑色邻居（8 邻域，即 $\max(|x-x'|,|y-y'|)=1$ ）时变为黑；一个操作前为黑的格子变为白。输出所有操作结束后每个格子的颜色。

思路

这是一个同步元胞自动机。直接模拟 $10^{100}$ 次显然不可能，关键在于发现它"很快进入周期为 2 的规律运动"。

核心观察 1：一次操作后得到的任何局面中，每个黑格都一定有一个白格邻居。因为一个格子操作后为黑，说明它操作前是白格且存在一个操作前为黑的相邻格子，而那个格子操作后已经变白。因此黑色永远不会"孤立"地停在原地，它会持续向四周传播。

核心观察 2（用 BFS 距离刻画）：先手动执行一次操作，得到局面 $S$ 。设 $d(v)$ 为格子 $v$ 到 $S$ 中最近黑格的 8 邻域最短距离（多源 BFS）。可以归纳证明：第 $1 + t$ 次操作结束后，格子 $v$ 为黑色当且仅当

d(v) \le t \quad \text{且} \quad d(v) \equiv t \pmod 2.

直观上： $d(v)$ 是"波"从最近的初始黑格传到 $v$ 需要的步数，所以 $v$ 在第 $1+d(v)$ 次操作首次变黑；由于每个黑格旁边永远有白格（观察 1）， $v$ 一旦变黑就从此黑白交替，即每隔一次操作翻转一次。归纳证明的本质是：邻居之间的 $d$ 值相差至多 $1$ ，因此"白格在下一轮变黑"恰好等价于其某个邻居本轮为黑且 $d$ 的奇偶性对上了。

代入 $10^{100}$ ： $10^{100}$ 是偶数，因此最终 $t = 10^{100} - 1$ 是奇数。条件 $d(v) \equiv t \pmod 2$ 等价于

\boxed{d(v) \text{ 为奇数 } \iff \text{ 最终为黑}}.

边界情况：若初始网格全为白，则一次操作后仍全白，BFS 无源，所有 $d(v)$ 视为无穷大，答案全白。实现时把"无穷大"设成一个偶数（例如 $10^9+10$ ），统一用奇偶性判断即可。

参考代码

#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> a(H);
    for (int i = 0; i < H; i++) cin >> a[i];

    const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
    const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
    auto in = [&](int x, int y) { return 0 <= x && x < H && 0 <= y && y < W; };

    // 先执行一次操作
    vector<string> b(H, string(W, '.'));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (a[i][j] == '.') {
                for (int d = 0; d < 8; d++) {
                    int x = i + dx[d], y = j + dy[d];
                    if (in(x, y) && a[x][y] == '#') { b[i][j] = '#'; break; }
                }
            }
        }
    }
    a = move(b);

    // 从当前黑格做多源 BFS
    const int INF = 1000000010;  // 偶数
    vector<vector<int>> D(H, vector<int>(W, INF));
    queue<pair<int, int>> q;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if (a[i][j] == '#') { D[i][j] = 0; q.push({i, j}); }

    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();
        for (int d = 0; d < 8; d++) {
            int x = i + dx[d], y = j + dy[d];
            if (in(x, y) && D[x][y] == INF) {
                D[x][y] = D[i][j] + 1;
                q.push({x, y});
            }
        }
    }

    // 距离为奇数 -> 黑
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) cout << (D[i][j] % 2 == 0 ? '.' : '#');
        cout << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(HW)$ （一次扫描 + 一次 BFS）
空间复杂度： $O(HW)$

E - x + y ≡ x + y

题目链接：https://atcoder.jp/contests/abc460/tasks/abc460_e

题目大意

定义 $\mathrm{concat}(a,b)$ 为把 $a$ 、 $b$ 的十进制表示拼接成的整数。给定 $N, M$ ，求满足

\mathrm{concat}(x, y) \equiv x + y \pmod M

且 $1 \le x, y \le N$ 的数对 $(x,y)$ 的数量，结果对 $998244353$ 取模。共 $T$ 组询问， $N \le 10^{18}$ ， $M \le 10^9$ 。

思路

设 $y$ 的十进制位数为 $d$ ，则

\mathrm{concat}(x, y) = x \cdot 10^d + y.

代入条件：

x \cdot 10^d + y \equiv x + y \pmod M \iff (10^d - 1)\,x \equiv 0 \pmod M.

关键结论：条件只与 $x$ 和 $d$ 有关，与 $y$ 的具体值无关！ 因此可以按 $d$ 分类统计。

固定 $d$ 。设 $g = \gcd(10^d - 1, M)$ ，方程 $(10^d - 1)x \equiv 0 \pmod M$ 等价于

\frac{M}{g} \;\Big|\; x, \qquad \text{即} \quad x \equiv 0 \pmod{M/g}.

所以在 $[1, N]$ 内满足条件的 $x$ 的个数为

\left\lfloor \frac{N}{M/g} \right\rfloor.

而恰有 $d$ 位的 $y$ （且 $y \le N$ ）的个数为

\max\left(0,\ \min(10^d - 1,\ N) - 10^{d-1} + 1\right).

令 $L = 10^{d-1}$ ， $R = \min(10^d,\ N+1)$ ，则个数为 $R - L$ （当 $R > L$ ）。于是

\text{答案} = \sum_{d=1}^{19} \left[ \max(0, \min(10^d, N+1) - 10^{d-1}) \cdot \left\lfloor \frac{N}{M/g_d} \right\rfloor \right] \bmod 998244353.

其中 $g_d = \gcd(10^d - 1, M)$ 。

范围与溢出： $N \le 10^{18}$ ，所以 $y$ 最多 19 位， $d \in [1, 19]$ 。计算 $10^{19}$ 时已经超出 64 位有符号整数范围，但 $10^{19} < 2^{64} \approx 1.84 \times 10^{19}$ ，用 unsigned long long 存储 $10^d$ 即可。 $M/g$ 与 $N$ 相除结果在 unsigned long long 范围内。

参考代码

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

using u64 = unsigned long long;

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

    const u64 mod = 998244353;
    const int dmax = 19;
    u64 p10[20];
    p10[0] = 1;
    for (int i = 1; i <= dmax; i++) p10[i] = p10[i - 1] * 10;

    int T;
    cin >> T;
    while (T--) {
        u64 N, M;
        cin >> N >> M;
        u64 ans = 0;
        for (int d = 1; d <= dmax; d++) {
            u64 L = p10[d - 1];
            u64 R = min(p10[d], N + 1);
            if (L >= R) break;
            u64 g = gcd(p10[d] - 1, M);
            u64 cntY = (R - L) % mod;                 // d 位 y 的个数
            u64 cntX = (N / (M / g)) % mod;           // 满足条件的 x 的个数
            ans = (ans + cntY * cntX) % mod;
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：每组 $O(19 \log M)$ （瓶颈是求 $\gcd$ ），即 $O(T \log N \log M)$ 量级
空间复杂度： $O(1)$

F - Farthest Pair Query

题目链接：https://atcoder.jp/contests/abc460/tasks/abc460_f

题目大意

有一棵 $N$ 个顶点的树，初始所有顶点都是黑色。处理 $Q$ 次查询：每次给出顶点 $x$ ，若 $x$ 为白则染黑，若为黑则染白，然后输出当前两个黑点之间距离的最大值。保证每次查询时至少存在两个黑点。

思路

设当前黑点集合为 $S$ ，问题就是求 $S$ 的直径（树上最远点对距离）。支持集合中单点加入/删除的动态直径问题，可以这样解决：

关键引理（直径合并）：设 $S, T$ 是非空点集， $S$ 的直径端点为 $a, b$ ， $T$ 的直径端点为 $c, d$ ，则 $S \cup T$ 的直径端点一定在 $\{a, b, c, d\}$ 中。也就是说，只比较这 4 个点两两之间的 $6$ 个距离，就能得到合并后集合的直径。

引理的证明依赖于下面这个性质：若 $u, v$ 是集合 $U$ 的直径端点，则对任意 $w \in U$ 与任意顶点 $x$ ，都有

d(x, w) \le \max\bigl(d(x, u),\, d(x, v)\bigr).

（这是"从某个点出发最远的点必为直径端点"的经典结论的推广：令 $p$ 为 $uv$ 路径上离 $w$ 最近的点、 $q$ 为 $uv$ 路径上离 $x$ 最近的点，利用 $u,v$ 是 $U$ 的直径可推出 $d(p,w) \le d(p,u), d(p,w) \le d(p,v)$ ，再结合 $q$ 位于 $up$ 或 $vp$ 段上即可。）

现在任取 $s \in S, t \in T$ ：对 $T$ 使用该性质得 $d(s,t) \le \max(d(s,c), d(s,d))$ ，再对 $S$ 使用性质得

d(s,t) \le \max\bigl(d(a,c),\, d(a,d),\, d(b,c),\, d(b,d)\bigr).

而 $S$ 内部两点距离至多 $d(a,b)$ ， $T$ 内部至多 $d(c,d)$ 。所以 $S \cup T$ 的直径确实由 $\{a,b,c,d\}$ 之间的 $6$ 个距离决定。故合并两个集合只需各自存一个直径端点对。

线段树维护：以顶点编号为下标建线段树。叶子：顶点 $v$ 为黑则存直径 $(v, v)$ ，为白则存"空"。合并时若一边为空取另一边；否则比较 $6$ 对距离取最大者。翻转一个点的颜色就是一次单点更新，根节点存储的就是全体黑点集合的直径，答案即两端点距离。

求距离：预处理深度，用 LCA 求距离， $d(u,v) = \mathrm{depth}[u] + \mathrm{depth}[v] - 2\,\mathrm{depth}[\mathrm{lca}(u,v)]$ 。这里用欧拉序 + 稀疏表实现 $O(1)$ 的 LCA（用二分上跳的 LCA 则每步 $O(\log N)$ ，也能通过）。每次合并要调用常数次距离，因此更新一次是 $O(\log N)$ 个节点 $\times$ 常数次 $O(1)$ 距离。

正确性：由引理，线段树每个节点维护的确实是其区间内黑点集合的直径；根节点的答案即为所求。注意保证"至少两个黑点"，所以根节点直径长度 $\ge 1$ 。

参考代码

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

int N;
vector<vector<int>> adj;
vector<int> depth, first, euler;
vector<vector<int>> st;  // 稀疏表：区间内深度最小的顶点

int lca(int u, int v) {
    int l = first[u], r = first[v];
    if (l > r) swap(l, r);
    int k = 31 - __builtin_clz(r - l + 1);
    int a = st[k][l], b = st[k][r - (1 << k) + 1];
    return depth[a] < depth[b] ? a : b;
}

ll dist(int u, int v) {
    int w = lca(u, v);
    return (ll)depth[u] + depth[v] - 2LL * depth[w];
}

// 线段树节点存直径端点 (u, v)，u = 0 表示集合为空
vector<int> segU, segV;
int SZ;

pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    if (a.first == 0) return b;
    if (b.first == 0) return a;
    int bu = a.first, bv = a.second;
    ll bd = dist(a.first, a.second);
    auto upd = [&](int x, int y) {
        ll d = dist(x, y);
        if (d > bd) { bd = d; bu = x; bv = y; }
    };
    upd(b.first, b.second);
    upd(a.first, b.first);
    upd(a.first, b.second);
    upd(a.second, b.first);
    upd(a.second, b.second);
    return {bu, bv};
}

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

    cin >> N;
    adj.assign(N + 1, {});
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 迭代式 DFS 构造欧拉序
    depth.assign(N + 1, 0);
    first.assign(N + 1, 0);
    {
        struct Frame { int v, p, d, state; };
        vector<Frame> stack;
        stack.push_back({1, 0, 0, 0});
        while (!stack.empty()) {
            auto [v, p, d, state] = stack.back();
            stack.pop_back();
            if (state == 0) {
                first[v] = (int)euler.size();
                euler.push_back(v);
                depth[v] = d;
                stack.push_back({v, p, d, 1});
                for (int i = (int)adj[v].size() - 1; i >= 0; i--) {
                    int u = adj[v][i];
                    if (u != p) stack.push_back({u, v, d + 1, 0});
                }
            } else {
                if (p != 0) euler.push_back(p);
            }
        }
    }

    // 稀疏表
    int L = (int)euler.size();
    int K = 0;
    while ((1 << K) <= L) K++;
    st.assign(K, vector<int>(L));
    for (int i = 0; i < L; i++) st[0][i] = euler[i];
    for (int k = 1; k < K; k++) {
        int len = 1 << (k - 1);
        for (int i = 0; i + (1 << k) <= L; i++) {
            int a = st[k - 1][i], b = st[k - 1][i + len];
            st[k][i] = depth[a] < depth[b] ? a : b;
        }
    }

    // 建直径线段树，初始全黑
    SZ = 1;
    while (SZ < N) SZ <<= 1;
    segU.assign(SZ * 2, 0);
    segV.assign(SZ * 2, 0);
    for (int v = 1; v <= N; v++) {
        segU[SZ + v - 1] = v;
        segV[SZ + v - 1] = v;
    }
    for (int p = SZ - 1; p >= 1; p--) {
        auto res = merge({segU[p * 2], segV[p * 2]}, {segU[p * 2 + 1], segV[p * 2 + 1]});
        segU[p] = res.first;
        segV[p] = res.second;
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int x;
        cin >> x;
        int p = SZ + x - 1;
        if (segU[p] == 0) {   // 白 -> 黑
            segU[p] = x;
            segV[p] = x;
        } else {              // 黑 -> 白
            segU[p] = 0;
            segV[p] = 0;
        }
        for (p >>= 1; p; p >>= 1) {
            auto res = merge({segU[p * 2], segV[p * 2]}, {segU[p * 2 + 1], segV[p * 2 + 1]});
            segU[p] = res.first;
            segV[p] = res.second;
        }
        cout << dist(segU[1], segV[1]) << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：预处理 $O(N \log N)$ （欧拉序 + 稀疏表 + 建树），每次查询 $O(\log N)$ ，总 $O((N+Q)\log N)$ （若用倍增 LCA 则为 $O((N+Q)\log^2 N)$ ）
空间复杂度： $O(N \log N)$

G - Vertex Flip Query

题目链接：https://atcoder.jp/contests/abc460/tasks/abc460_g

题目大意

有一棵 $N$ 个顶点的树，顶点 $i$ 有权重 $W_i$ 和颜色 $C_i \in \{0,1\}$ 。处理 $Q$ 次操作：

1 v：翻转顶点 $v$ 的颜色（ $C_v \leftarrow 1 - C_v$ ）；
2 v x：把 $W_v$ 增加 $x$ ；
3 v：输出从 $v$ 出发、只经过颜色为 $C_v$ 的顶点所能到达的所有顶点（含 $v$ 自身）的权值之和。

思路

查询要求的是" $v$ 所在同色连通块"的权值和，而翻转颜色会实时改变连通块的结构。官方题解使用的是静态 top tree（把树像线段树一样递归分解成簇，在每个簇上同时维护自底向上与自顶向下的换根 DP 信息），单次操作 $O(\log N)$ 。下面给出另一种可行且实现直观的做法：HLD + 链上线段树维护换根 DP，单次操作 $O(\log^2 N)$ ，也能通过本题限制。

第一步：把查询转化为"子树 DP 值 + 找同色段顶端"

把树定根为 $1$ 。对每个顶点 $v$ 定义子树 DP：

f(v) = W_v + \sum_{\substack{u \text{ 是 } v \text{ 的孩子} \\ C_u = C_v}} f(u),

即 $f(v)$ 是"在子树 $v$ 内部、 $v$ 所在同色连通块的权值和"。定义 $\mathrm{anc}(v)$ 为从 $v$ 出发向上走、只要边两端同色就一直走，最终到达的最高顶点（即路径 $v \to \mathrm{anc}(v)$ 上的边全部同色，且 $\mathrm{anc}(v)$ 的父边不同色或 $\mathrm{anc}(v)=1$ ）。

结论：查询 3 v 的答案就是 $f(\mathrm{anc}(v))$ 。

证明：设 $\mathrm{up}(v)$ 表示 $v$ 所在同色连通块在子树 $v$ 之外的部分的权值和。若边 $(v, \mathrm{par}(v))$ 不同色，则 $\mathrm{up}(v)=0$ ；否则令

T(p) = W_p + \sum_{C_w = C_p} f(w) + \mathrm{up}(p),

有 $\mathrm{up}(v) = T(\mathrm{par}(v)) - f(v)$ 。不断上推，到 $\mathrm{anc}(v)$ 处 $\mathrm{up}=0$ ，故

\mathrm{ans}(v) = f(v) + \mathrm{up}(v) = T(\mathrm{anc}(v)) = W_{\mathrm{anc}(v)} + \sum_{C_w = C_{\mathrm{anc}(v)}} f(w) = f(\mathrm{anc}(v)).

于是问题化简为两件事：维护所有 $f(v)$ ，以及快速求出 $\mathrm{anc}(v)$ 。

第二步：用 HLD 维护 $f$

把 $f(v)$ 拆成"重孩子贡献 + 其余"：

f(v) = \underbrace{[C_v = C_{h_v}]}_{k_v}\cdot f(h_v) + \underbrace{W_v + \mathrm{light}_{C_v}(v)}_{b_v},

其中 $h_v$ 是 $v$ 的重孩子， $\mathrm{light}_c(v) = \sum f(u)$ （ $u$ 遍历 $v$ 的轻孩子中 $C_u = c$ 者）。

每条重链上的递推是仿射变换：给定下方顶点的 $f$ 值 $x$ ，本顶点输出 $k_v x + b_v$ 。仿射变换的合成仍是仿射变换，两段（上段 L、下段 R）合成为

(k_L, b_L) \circ (k_R, b_R) = (k_L k_R,\; k_L b_R + b_L).

用一棵线段树维护每条链的叶子 $(k_v, b_v)$ ：单点修改、区间查询合成变换， $O(\log N)$ 得到任意 $v$ 的 $f(v)$ （链的最底端没有重孩子，其 $k=0$ ，故把整段变换作用在 $0$ 上取 $b$ 分量即可，链头的 $f$ 即整条链变换的 $b$ ）。 $\mathrm{light}_c(v)$ 作为辅助量单独维护：某个轻孩子 $u$ 的 $f(u)$ 变化 $\Delta$ 时，同步修改 $\mathrm{light}_{C_u}(\mathrm{par}(u))$ 。

变化的传播： $v$ 的权值或颜色改变导致 $f(v)$ 变化时，该变化沿"同色路径"向上传播：同一重链内由仿射合成自动吸收；当传播到链头 $h$ 时，若边 $(h, \mathrm{par}(h))$ 同色，就把 $\Delta$ 加进 $\mathrm{light}_{C_h}(\mathrm{par}(h))$ 、更新 $\mathrm{par}(h)$ 的叶子并重算其所在链，继续上推。由于每条根路径上的轻边至多 $O(\log N)$ 条，一次传播 $O(\log^2 N)$ 。

三种操作的实现

操作 2（加权）： $W_v \mathrel{+}= x$ ，更新叶子 $(k_v, b_v)$ ，重算 $v$ 所在链并向上传播。
操作 1（翻色）：设旧色 $c$ $c$ 、新色 $\bar c$ $\overset{c}{ˉ}$ 。
1. 若 $v$ 是父亲的轻孩子（即 $v$ 是链头），把 $f(v)$ （即链头当前值）从 $\mathrm{light}_c(\mathrm{par}(v))$ 挪到 $\mathrm{light}_{\bar c}(\mathrm{par}(v))$ ；
2. 更新 $v$ 的叶子： $C_v = \bar c$ ， $k_v = [C_{h_v} = \bar c]$ ， $b_v = W_v + \mathrm{light}_{\bar c}(v)$ ；
3. 若 $v$ 是父亲的重孩子，父亲叶子的 $k$ 也会随之变化，一并更新；
4. 重算 $v$ 所在链并向上传播，同时更新"颜色线段树"。
操作 3（查询）：先在颜色线段树上找到 $\mathrm{anc}(v)$ ——在 $v$ 所在链内做"找区间最右异色位置"的线段树下钻，得到同色段的顶端；若顶端恰为链头且父边同色，则跨到父链继续；如此跨过 $O(\log N)$ 条链。最后查询 $f(\mathrm{anc}(v))$ 并输出。

复杂度

预处理 $O(N \log N)$ ，每次操作 $O(\log^2 N)$ ，总复杂度 $O((N+Q)\log^2 N)$ 。官方静态 top tree 的做法可优化到 $O((N+Q)\log N)$ 。

参考代码

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

int N, Q;
vector<ll> W;
vector<int> C;

vector<vector<int>> adj;
vector<int> parent, sz, heavyV;    // heavyV[v] = v 的重孩子，0 表示没有
vector<int> head, pos, vertexAt;   // 链头、DFS 序位置、位置的顶点
vector<int> chainStart, chainEnd;  // 每条链（按链头顶点索引）的起止位置

vector<ll> light0, light1;  // light[v][c]
vector<ll> headF;           // 每条链链头的 f 值

// ---- 链 DP 线段树（仿射变换 (k, b)，f(x) = k*x + b）----
int SZ;
vector<int> kk;
vector<ll> bb;

inline int getK(int v) { return (heavyV[v] && C[heavyV[v]] == C[v]) ? 1 : 0; }
inline ll getB(int v) { return W[v] + (C[v] == 0 ? light0[v] : light1[v]); }

void dpUpdateLeaf(int v) {
    int p = pos[v] + SZ;
    kk[p] = getK(v);
    bb[p] = getB(v);
    for (p >>= 1; p; p >>= 1) {
        int L = p << 1, R = L | 1;
        kk[p] = kk[L] * kk[R];
        bb[p] = (ll)kk[L] * bb[R] + bb[L];
    }
}

pair<int, ll> dpQuery(int l, int r) {  // 区间 [l, r) 按位置顺序合成
    int kl = 1; ll bl = 0;
    int kr = 1; ll br = 0;
    l += SZ; r += SZ;
    while (l < r) {
        if (l & 1) {
            int k2 = kl * kk[l];
            ll b2 = (ll)kl * bb[l] + bl;
            kl = k2; bl = b2;
            l++;
        }
        if (r & 1) {
            --r;
            int k2 = kk[r] * kr;
            ll b2 = (ll)kk[r] * br + bb[r];
            kr = k2; br = b2;
        }
        l >>= 1; r >>= 1;
    }
    return {kl * kr, (ll)kl * br + bl};
}

// ---- 颜色线段树：allSame[node] = 整段统一颜色，否则 -1 ----
vector<int> allSame;

void colorBuild(int node, int l, int r) {
    if (l == r) { allSame[node] = C[vertexAt[l]]; return; }
    int mid = (l + r) >> 1;
    colorBuild(node * 2, l, mid);
    colorBuild(node * 2 + 1, mid + 1, r);
    allSame[node] = (allSame[node * 2] == allSame[node * 2 + 1]) ? allSame[node * 2] : -1;
}

void colorUpdate(int node, int l, int r, int p) {
    if (l == r) { allSame[node] = C[vertexAt[p]]; return; }
    int mid = (l + r) >> 1;
    if (p <= mid) colorUpdate(node * 2, l, mid, p);
    else colorUpdate(node * 2 + 1, mid + 1, r, p);
    allSame[node] = (allSame[node * 2] == allSame[node * 2 + 1]) ? allSame[node * 2] : -1;
}

int findRightmostNot(int node, int l, int r, int ql, int qr, int c) {
    if (r < ql || qr < l) return -1;
    if (ql <= l && r <= qr) {
        if (allSame[node] == c) return -1;
        if (allSame[node] != -1) return r;  // 整段统一且异色
    }
    int mid = (l + r) >> 1;
    int res = findRightmostNot(node * 2 + 1, mid + 1, r, ql, qr, c);
    if (res != -1) return res;
    return findRightmostNot(node * 2, l, mid, ql, qr, c);
}

// 重算链 h 的链头 f，并把变化量向上传播
void recomputeChain(int h) {
    auto res = dpQuery(chainStart[h], chainEnd[h] + 1);
    ll newF = res.second;
    ll delta = newF - headF[h];
    headF[h] = newF;
    if (delta != 0 && h != 1) {
        int p = parent[h];
        if (C[h] == 0) light0[p] += delta; else light1[p] += delta;
        if (C[h] == C[p]) {
            dpUpdateLeaf(p);
            recomputeChain(head[p]);
        }
    }
}

void flipColor(int v) {
    int old = C[v], nw = old ^ 1;
    if (v != 1 && head[v] == v) {   // v 是父亲的轻孩子（链头）：颜色桶转移
        int p = parent[v];
        if (old == 0) light0[p] -= headF[v]; else light1[p] -= headF[v];
        if (nw == 0) light0[p] += headF[v]; else light1[p] += headF[v];
        dpUpdateLeaf(p);
        recomputeChain(head[p]);
    }
    C[v] = nw;
    dpUpdateLeaf(v);
    colorUpdate(1, 0, N - 1, pos[v]);
    if (v != 1 && head[v] != v) {   // v 是父亲的重孩子：父亲的 k 会变
        dpUpdateLeaf(parent[v]);
    }
    recomputeChain(head[v]);
}

void addWeight(int v, ll x) {
    W[v] += x;
    dpUpdateLeaf(v);
    recomputeChain(head[v]);
}

int getAnc(int v) {   // 找 v 的同色段顶端
    int c = C[v], x = v;
    while (true) {
        int h = head[x];
        int j = findRightmostNot(1, 0, N - 1, chainStart[h], pos[x], c);
        int top = (j == -1) ? chainStart[h] : j + 1;
        int u = vertexAt[top];
        if (u != 1 && top == chainStart[h] && C[parent[u]] == c) {
            x = parent[u];   // 同色段顶到链头且父边同色，继续跨链
        } else {
            return u;
        }
    }
}

ll query3(int v) {
    int u = getAnc(v);
    auto res = dpQuery(pos[u], chainEnd[head[u]] + 1);
    return res.second;
}

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

    cin >> N >> Q;
    W.assign(N + 1, 0);
    C.assign(N + 1, 0);
    for (int i = 1; i <= N; i++) cin >> W[i];
    for (int i = 1; i <= N; i++) cin >> C[i];
    adj.assign(N + 1, {});
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    parent.assign(N + 1, 0);
    sz.assign(N + 1, 0);
    heavyV.assign(N + 1, 0);

    // 迭代 DFS 得到先序，反向后用于自底向上
    vector<int> order;
    order.reserve(N);
    {
        vector<int> stk{1};
        while (!stk.empty()) {
            int v = stk.back();
            stk.pop_back();
            order.push_back(v);
            for (int u : adj[v]) if (u != parent[v]) {
                parent[u] = v;
                stk.push_back(u);
            }
        }
    }
    for (int i = N - 1; i >= 0; i--) {   // 子树大小与重孩子
        int v = order[i];
        sz[v] = 1;
        int best = 0, bs = 0;
        for (int u : adj[v]) if (parent[u] == v) {
            sz[v] += sz[u];
            if (sz[u] > bs) { bs = sz[u]; best = u; }
        }
        heavyV[v] = best;
    }

    head.assign(N + 1, 0);
    pos.assign(N + 1, 0);
    vertexAt.assign(N, 0);
    chainStart.assign(N + 1, 0);
    chainEnd.assign(N + 1, 0);
    {   // 剖分：每条链占据一段连续位置
        int cur = 0;
        vector<pair<int, int>> stk2{{1, 1}};  // (顶点, 链头)
        while (!stk2.empty()) {
            auto [v, h] = stk2.back();
            stk2.pop_back();
            chainStart[h] = cur;
            for (int x = v; x != 0; x = heavyV[x]) {
                head[x] = h;
                pos[x] = cur;
                vertexAt[cur] = x;
                cur++;
                for (int u : adj[x]) if (parent[u] == x && u != heavyV[x]) {
                    stk2.push_back({u, u});
                }
            }
            chainEnd[h] = cur - 1;
        }
    }

    // 自底向上求初始 f 与 light 桶
    vector<ll> f(N + 1, 0);
    light0.assign(N + 1, 0);
    light1.assign(N + 1, 0);
    for (int i = N - 1; i >= 0; i--) {
        int v = order[i];
        f[v] = W[v] + (C[v] == 0 ? light0[v] : light1[v]);
        if (heavyV[v] && C[heavyV[v]] == C[v]) f[v] += f[heavyV[v]];
        int p = parent[v];
        if (p && heavyV[p] != v) {
            if (C[v] == 0) light0[p] += f[v]; else light1[p] += f[v];
        }
    }
    headF.assign(N + 1, 0);
    for (int v = 1; v <= N; v++) if (head[v] == v) headF[v] = f[v];

    // 链 DP 线段树
    SZ = 1;
    while (SZ < N) SZ <<= 1;
    kk.assign(SZ * 2, 1);
    bb.assign(SZ * 2, 0);
    for (int v = 1; v <= N; v++) {
        kk[SZ + pos[v]] = getK(v);
        bb[SZ + pos[v]] = getB(v);
    }
    for (int p = SZ - 1; p >= 1; p--) {
        int L = p << 1, R = L | 1;
        kk[p] = kk[L] * kk[R];
        bb[p] = (ll)kk[L] * bb[R] + bb[L];
    }

    // 颜色线段树
    allSame.assign(N * 4, 0);
    colorBuild(1, 0, N - 1);

    while (Q--) {
        int t, v;
        cin >> t >> v;
        if (t == 1) {
            flipColor(v);
        } else if (t == 2) {
            ll x;
            cin >> x;
            addWeight(v, x);
        } else {
            cout << query3(v) << '\n';
        }
    }
    return 0;
}

复杂度分析

时间复杂度：预处理 $O(N \log N)$ ；每次操作 $O(\log^2 N)$ ，总 $O((N+Q)\log^2 N)$
空间复杂度： $O(N)$