AtCoder Beginner Contest 451 题解

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

AtCoder Beginner Contest 451 题解

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

比赛概览

本场整体难度中等偏基础。A、B 属于签到与简单计数，C 是典型的优先队列（堆）模拟，重点在于理解"每棵树只会被删除一次"的均摊分析；D 考验对枚举规模的估计与按位数递推；E 考察"距离矩阵 → 树"的构造与验证思维；F 是 DSU 按大小合并（small-to-large）的经典动态图二分性问题；G 综合了线性基（XOR basis）与二进制 Trie，是全场的压轴题。建议重点掌握 C 的均摊复杂度分析、F 的按大小合并技巧，以及 G 的"最小 XOR 路径权化为线性基 + Trie"这一经典套路。

A - illegal

题目链接：https://atcoder.jp/contests/abc451/tasks/abc451_a

题目大意

给定一个由小写字母组成的字符串 $S$ （长度在 $1$ 到 $10$ 之间）。若 $S$ 的长度是 $5$ 的倍数，则高桥违反法律，输出 Yes；否则输出 No。

思路

题目本质就是判断 $|S| \bmod 5 = 0$ 是否成立。这与字符串的内容完全无关，只需要取 S.size() 对 $5$ 取模即可。

注意长度为 $0$ 的情形不可能出现（约束保证长度至少为 $1$ ），因此不必特殊处理；直接判断即可。

参考代码

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

int main() {
    string s;
    cin >> s;
    cout << (s.size() % 5 == 0 ? "Yes" : "No") << '\n';
    return 0;
}

s = input()
print("Yes" if len(s) % 5 == 0 else "No")

复杂度分析

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

B - Personnel Change

题目链接：https://atcoder.jp/contests/abc451/tasks/abc451_b

题目大意

公司有 $N$ 名员工，编号 $1 \sim N$ ；有 $M$ 个部门，编号 $1 \sim M$ 。员工 $i$ 本学期在部门 $A_i$ ，下学期将转到部门 $B_i$ 。对每个部门 $j$ ，求"下学期人数减去本学期人数"。

思路

每个部门的净变化量等于"转入人数 $-$ 转出人数"。每名员工独立地贡献一个 $-1$ （离开 $A_i$ ）和一个 $+1$ （加入 $B_i$ ），互不干扰，因此用一个长度为 $M$ 的差分数组即可：

\text{diff}[A_i] \mathrel{-}= 1,\qquad \text{diff}[B_i] \mathrel{+}= 1.

处理完所有员工后， $\text{diff}[j]$ 即为部门 $j$ 的答案。注意部门编号从 $1$ 开始，数组下标相应偏移。

正确性： $\text{diff}[j]$ 统计的是"下学期属于 $j$ 的人数 $-$ 本学期属于 $j$ 的人数"，正是题目所求，每个员工的贡献线性叠加。

参考代码

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> diff(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        int A, B;
        cin >> A >> B;
        diff[A]--;   // 本学期离开部门 A
        diff[B]++;   // 下学期加入部门 B
    }
    for (int j = 1; j <= M; ++j) cout << diff[j] << '\n';
    return 0;
}

N, M = map(int, input().split())
ans = [0] * M
for _ in range(N):
    A, B = map(int, input().split())
    ans[A - 1] -= 1
    ans[B - 1] += 1
for v in ans:
    print(v)

复杂度分析

时间复杂度： $O(N + M)$
空间复杂度： $O(M)$

C - Understory

题目链接：https://atcoder.jp/contests/abc451/tasks/abc451_c

题目大意

高桥管理花园里的树，初始没有树。有 $Q$ 次操作：

1 h：向花园中加入一棵高度为 $h$ 的树；
2 h：删除当前所有高度不超过 $h$ 的树。

每次操作结束后，输出当前花园中树的数量。 $1 \le Q \le 3 \times 10^5$ ， $1 \le h \le 10^9$ 。

思路

关键观察：每棵树最多只会被删除一次。 因此所有操作 2 累计弹出的树的总数不超过操作 1 插入的总数，即 $O(Q)$ 。这保证了"操作 2 反复弹出"的做法总体是高效的。

用最小堆维护当前存活树的高度：

操作 1：把 $h$ 压入堆；
操作 2：不断检查堆顶，只要堆顶 $\le h$ 就弹出，直到堆空或堆顶 $> h$ ；
每次操作后输出堆的大小。

正确性：最小堆的堆顶是当前所有存活树中的最小高度。若堆顶 $> h$ ，则说明所有树的高度都 $> h$ ，没有任何树需要删除，循环终止；若堆顶 $\le h$ ，则该树一定属于"高度不超过 $h$ "的集合，删除它不会漏删。所以"弹出所有 $\le h$ 的堆顶"恰好删除了所有应删的树。

时间复杂度分析：插入 $O(Q)$ 次，每次 $O(\log Q)$ ；删除总数 $O(Q)$ 次，每次 $O(\log Q)$ ；加上每次查询堆顶 $O(1)$ 。总复杂度 $O(Q \log Q)$ 。

易错点：C++ 的 priority_queue 默认是大根堆，本题需要取最小元素，要写成 priority_queue<int, vector<int>, greater<int>>；每次操作后都要输出（包括操作 1 之后）。数据范围下高度用 int 即可（ $10^9 < 2^{31}$ ）。

参考代码

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

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

    int Q;
    cin >> Q;
    priority_queue<int, vector<int>, greater<int>> pq;   // 最小堆
    while (Q--) {
        int t, h;
        cin >> t >> h;
        if (t == 1) {
            pq.push(h);
        } else {
            while (!pq.empty() && pq.top() <= h) pq.pop();
        }
        cout << pq.size() << '\n';
    }
    return 0;
}

from heapq import heappop, heappush

que = []
q = int(input())
for _ in range(q):
    t, h = map(int, input().split())
    if t == 1:
        heappush(que, h)
    else:
        while que and que[0] <= h:
            heappop(que)
    print(len(que))

复杂度分析

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

D - Concat Power of 2

题目链接：https://atcoder.jp/contests/abc451/tasks/abc451_d

题目大意

若一个正整数可以由若干 $2$ 的幂（ $1,2,4,8,16,\dots$ ）的十进制表示拼接而成（允许重复、乱序），则称之为"好整数"。给定 $N$ ，求第 $N$ 小的好整数。保证第 $N$ 小的好整数不超过 $10^9$ 。

例如前几个好整数为 $1,2,4,8,11,12,14,16,18,21,\dots$ （ $11 = 1|1$ ， $12 = 1|2$ ， $14 = 1|4$ ， $18 = 1|8$ ， $21 = 2|1$ ，……）。

思路

关键观察 1：不超过 $10^9$ 的好整数数量并不多。 由样例 3（第 $1099898$ 个好整数约为 $0.8 \times 10^9$ ）可以推测总量在百万量级，直接全部枚举后排序是可行的。

关键观察 2： $10^9$ 本身不是好整数。 任何 $2$ 的幂的个位数字属于 $\{1,2,4,8,6\}$ ，而拼接结果的个位等于最后一块 $2$ 的幂的个位，因此好整数的个位只能是 $1,2,4,8,6$ 之一； $10^9 = 1000000000$ 个位为 $0$ ，故不是好整数。因此"不超过 $10^9$ 的好整数"等价于"至多 $9$ 位的好整数"，只需要枚举位数 $k=1,\dots,9$ 。

按位数递推。 设：

$X_k$ ：恰好 $k$ 位的好整数组成的集合；
$P_k$ ：恰好 $k$ 位的 $2$ 的幂组成的集合；
规定 $X_0 = \{0\}$ 。

任意 $k$ 位好整数都可以看成"一个 $(k-i)$ 位好整数"后接"一个 $i$ 位 $2$ 的幂"，故对 $k \ge 1$ ：

X_k = \bigcup_{i=1}^{k} \left\{ x \cdot 10^i + p \;\middle|\; x \in X_{k-i},\ p \in P_i \right\}.

$P_k$ 的求法。 $2^e$ 恰好有 $k$ 位当且仅当

10^{k-1} \le 2^e < 10^k \iff \mathrm{bitlen}(10^{k-1}-1) \le e < \mathrm{bitlen}(10^k - 1),

其中 $\mathrm{bitlen}(m)$ 表示 $m$ 的二进制位数（ $\lfloor \log_2 m \rfloor + 1$ ）。

规模估计。 由于 $|P_i| \le \lceil \log_2 10 \rceil = 4$ ，可得

S_k - S_{k-1} = |X_k| \le \sum_{i=1}^{k} |X_{k-i}| \cdot |P_i| \le 4(S_{k-1}+1),

其中 $S_k = |X_1| + \cdots + |X_k|$ ，进而 $S_k + 1 \le 5(S_{k-1}+1) \le \dots \le 5^k$ ，即至多 $5^9 - 1 = 1953124$ 个。实际枚举得到恰好 $1257874$ 个不超过 $10^9$ 的好整数，完全在时限内。

最后把所有 $X_1,\dots,X_9$ 中的数收集起来排序（集合本身保证去重），输出第 $N$ 个即可。

注意：用 long long 存值（ $x \cdot 10^i + p$ 最大接近 $10^9$ ）； $N$ 保证不超过总数，所以数组不会越界。

参考代码

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

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

    long long pw10[10] = {1, 10, 100, 1000, 10000, 100000,
                          1000000, 10000000, 100000000, 1000000000};
    auto bitlen = [](long long x) { return 64 - __builtin_clzll(x); };  // x > 0

    // P[k]: 恰好 k 位的所有 2 的幂 (1 <= k <= 9)
    vector<vector<long long>> P(10);
    for (int k = 1; k <= 9; ++k) {
        int l = (k == 1) ? 0 : bitlen(pw10[k - 1] - 1);
        int r = bitlen(pw10[k] - 1);
        for (int e = l; e < r; ++e) P[k].push_back(1LL << e);
    }

    // X[k]: 恰好 k 位的好整数集合
    vector<set<long long>> X(10);
    X[0].insert(0);
    vector<long long> all;
    for (int k = 1; k <= 9; ++k) {
        for (int i = 1; i <= k; ++i) {
            for (long long x : X[k - i]) {
                for (long long p : P[i]) {
                    X[k].insert(x * pw10[i] + p);
                }
            }
        }
        for (long long v : X[k]) all.push_back(v);
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());

    int N;
    cin >> N;
    cout << all[N - 1] << '\n';
    return 0;
}

P = [[] for _ in range(10)]
for k in range(1, 10):
    l = (10 ** (k - 1) - 1).bit_length()
    r = (10 ** k - 1).bit_length()
    P[k] = [1 << i for i in range(l, r)]

X = [set() for _ in range(10)]
X[0] = {0}
A = []
for k in range(1, 10):
    for i in range(1, k + 1):
        X[k] |= {x * (10 ** i) + p for x in X[k - i] for p in P[i]}
    A += list(X[k])
A.sort()

N = int(input())
print(A[N - 1])

复杂度分析

时间复杂度： $O(T \log T)$ ，其中 $T = 1257874$ 为不超过 $10^9$ 的好整数总数（枚举与排序均在百万量级）
空间复杂度： $O(T)$

E - Tree Distance

题目链接：https://atcoder.jp/contests/abc451/tasks/abc451_e

题目大意

给定 $N$ 个点的"全点对距离"矩阵 $A$ （输入给出 $i < j$ 的 $A_{i,j}$ ），问是否存在一棵带权无向树，使得任意两个点 $i,j$ 在树上的距离恰好等于 $A_{i,j}$ 。距离定义为路径上边权之和。 $2 \le N \le 3000$ ， $1 \le A_{i,j} \le 9999$ 。

思路

问题转化：把"是否存在"变成"先构造、再验证"。 若存在这样的树，它其实可以被唯一地构造出来；若构造出的树验证失败，则答案就是 No。

关键观察 1（祖先判别）： 以顶点 $1$ 为根。在边权均为正的树上，对任意点 $i$ ，有三角不等式

A_{1,j} + A_{j,i} \ge A_{1,i},

等号成立当且仅当 $j$ 位于 $1$ 到 $i$ 的路径上，即 $j$ 是 $i$ 的祖先（或 $j = i$ ）。因此集合

S_i = \left\{ j \ne i \;\middle|\; A_{1,j} + A_{j,i} = A_{1,i} \right\}

恰好是 $i$ 的所有祖先（含根 $1$ ）。特别地， $j=1$ 时 $A_{1,1} + A_{1,i} = 0 + A_{1,i}$ 恒成立，所以 $S_i$ 永远非空。

关键观察 2（父节点）： $i$ 的父节点是 $S_i$ 中离 $i$ 最近的那个祖先，即

p_i = \mathop{\arg\min}_{j \in S_i} A_{i,j},

边权为 $A_{i,p_i}$ 。在真实存在的树里，这个最小值是唯一取在父节点上的（对任意其他祖先 $j$ ， $A_{i,j} = A_{i,p_i} + A_{p_i,j} > A_{i,p_i}$ ）。因此：

若矩阵确实来自一棵树，上述构造必定还原出这棵唯一的树；
若 $S_i$ 中并列存在多个最小者，说明矩阵不来自树，此时随意取一个（如第一次遇到的最小者），最终会由验证步骤发现矛盾。

构造： 对每个 $i = 2, \dots, N$ ，扫描 $j$ 求出 $p_i$ ，加入边 $(i, p_i, A_{i,p_i})$ 。共 $N-1$ 条边；由于每条边都指向 $A_{1,\cdot}$ 严格更小的点，结构必然连通，是一棵以 $1$ 为根的树。

验证： 从每个点 $s$ 出发做 BFS/DFS，算出到所有点的距离，逐项与 $A_{s,\cdot}$ 比较。全部一致输出 Yes，否则 No。构造 $O(N^2)$ ，验证 $O(N^2)$ ，总复杂度 $O(N^2)$ ，对 $N \le 3000$ 完全可行。

为什么正确： 若 $A$ 可实现，构造出的树就是那棵唯一的树，验证必然通过；若 $A$ 不可实现，无论构造出什么样的候选树（甚至可能是"看起来合理"的树），其距离矩阵必然在某处与 $A$ 不一致，验证必然失败。因此"构造 + 验证"与"存在性判断"是等价的。

参考代码

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

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

    int N;
    cin >> N;
    vector<vector<int>> A(N + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            cin >> A[i][j];
            A[j][i] = A[i][j];          // 对称填充
        }
    }
    // A[1][1] = 0 已由初始化保证

    vector<vector<pair<int, int>>> adj(N + 1);   // (邻居, 边权)
    bool ok = true;
    for (int i = 2; i <= N && ok; ++i) {
        int bestJ = -1, bestD = INT_MAX;
        for (int j = 1; j <= N; ++j) {
            if (j == i) continue;
            if (A[1][j] + A[j][i] == A[1][i]) {  // j 是 i 的潜在祖先
                if (A[i][j] < bestD) {
                    bestD = A[i][j];
                    bestJ = j;
                }
            }
        }
        if (bestJ == -1) { ok = false; break; }  // 防御性判断（实际不会发生）
        adj[i].push_back({bestJ, bestD});
        adj[bestJ].push_back({i, bestD});
    }

    // 验证：从每个源点 BFS，比对全部距离
    if (ok) {
        for (int s = 1; s <= N; ++s) {
            vector<int> dist(N + 1, -1);
            queue<int> q;
            dist[s] = 0;
            q.push(s);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (auto [v, w] : adj[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + w;
                        q.push(v);
                    }
                }
            }
            for (int t = 1; t <= N; ++t) {
                if (dist[t] != A[s][t]) { ok = false; break; }
            }
            if (!ok) break;
        }
    }

    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N^2)$ （构造扫描所有点对 + 每个源点 BFS 一次，各 $O(N^2)$ ）
空间复杂度： $O(N^2)$ （存储距离矩阵与邻接表）

F - Make Bipartite 3

题目链接：https://atcoder.jp/contests/abc451/tasks/abc451_f

题目大意

初始有一个 $N$ 个顶点、零条边的无向图。按顺序加入 $Q$ 条边 $(u_i, v_i)$ 。每次加边后，问是否存在一种将顶点染成白/黑的方案，使每条边的两端颜色不同；若存在，求出最少需要染黑多少个顶点；若不存在，输出 $-1$ 。 $2 \le N \le 2 \times 10^5$ ， $1 \le Q \le 2 \times 10^5$ ，无重边。

思路

静态问题的答案： 给定一个图，若它不是二分图则答案为 $-1$ ；若它是二分图，则每个连通分量恰好有两种染色方案（整体黑白互换），每种方案的黑点数分别为 $|\text{白}|$ 与 $|\text{黑}|$ 。由于各分量独立，答案为

\sum_{\text{连通分量}} \min\left(|白|,\ |黑|\right).

逐条加边的影响： 加一条边 $(u,v)$ 只会影响 $u,v$ 所在的两个连通分量。

$u,v$ 在同一分量内： 若 $u,v$ 当前颜色不同，则无事发生；若颜色相同，则这条边连接同色两点，会形成一个奇环，图从此不再二分，此后永远输出 $-1$ （加边不会消除已存在的奇环）。
$u,v$ 在不同分量内： 合并两个分量必然仍为二分图。若 $u,v$ 当前颜色不同，直接合并即可；若颜色相同，则把其中一个分量的染色整体翻转后再合并，就能使 $u,v$ 异色。

按大小合并（small-to-large）： 翻转一个分量、把它的顶点并入另一个分量，代价正比于该分量的顶点数。朴素地在合并时遍历任意一个分量最坏 $O(N^2)$ 。技巧是只翻转/遍历较小的分量：固定一个顶点，它每次被遍历时所在分量的大小至少翻倍，因此每个顶点最多被遍历 $O(\log N)$ 次，总代价 $O(N \log N)$ 。

实现： 用并查集（DSU）维护连通性；每个分量的根维护两个集合 white / black（本实现用 std::set<int>），同时用数组 color 记录每个顶点的当前颜色（ $0$ 白 / $1$ 黑）。维护全局答案 ans 为当前所有分量 $\min(|白|,|黑|)$ 之和：

合并前先减去两个分量的贡献；
保证 lu 为较大分量；若 color[u] == color[v]，则整体翻转较小分量 lv（交换两个集合并更新 color）；
把 lv 的同色集合并入 lu 的对应集合；
DSU 合并，再加上新分量的贡献。

正确性：每次合并都显式保证了新边 $(u,v)$ 两端异色，且分量的其他边不受影响（整体翻转不改变任何端点颜色关系）；当且仅当出现"同分量同色"时图变为非二分图，答案置为 $-1$ 。

易错点： 一旦 ans == -1，后续查询仍要读入输入并直接输出 -1，不能跳过读取。

参考代码

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

struct DSU {
    vector<int> par, sz;
    DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }
    int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);   // 始终保持 x 为较大根
        par[y] = x;
        sz[x] += sz[y];
    }
    int size(int x) { return sz[find(x)]; }
};

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

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

    DSU dsu(N + 1);
    vector<set<int>> white(N + 1), black(N + 1);
    vector<int> color(N + 1, 0);                 // 0 白 / 1 黑
    for (int i = 1; i <= N; ++i) white[i].insert(i);

    long long ans = 0;                           // 当前 sum of min(|white|,|black|)
    for (int qi = 0; qi < Q; ++qi) {
        int u, v;
        cin >> u >> v;
        if (ans == -1) {
            cout << -1 << '\n';
            continue;
        }
        int lu = dsu.find(u), lv = dsu.find(v);
        if (lu == lv) {
            if (color[u] == color[v]) ans = -1;  // 出现奇环，从此无解
        } else {
            ans -= (long long)min(white[lu].size(), black[lu].size());
            ans -= (long long)min(white[lv].size(), black[lv].size());

            if (dsu.size(lu) < dsu.size(lv)) {   // 让 lu 为较大分量
                swap(lu, lv);
                swap(u, v);
            }
            if (color[u] == color[v]) {          // 整体翻转较小分量 lv
                swap(white[lv], black[lv]);
                for (int x : white[lv]) color[x] = 0;
                for (int x : black[lv]) color[x] = 1;
            }
            for (int x : white[lv]) white[lu].insert(x);
            for (int x : black[lv]) black[lu].insert(x);
            white[lv].clear();
            black[lv].clear();

            dsu.unite(lu, lv);
            ans += (long long)min(white[lu].size(), black[lu].size());
        }
        cout << ans << '\n';
    }
    return 0;
}

# 自包含实现（无需外部库），思路与上方 C++ 一致
import sys

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
        self.sz = [1] * n
    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return x
        if self.sz[x] < self.sz[y]:
            x, y = y, x
        self.par[y] = x
        self.sz[x] += self.sz[y]
        return x

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    dsu = DSU(N)
    white = [set() for _ in range(N)]
    black = [set() for _ in range(N)]
    color = [0] * N
    for i in range(N):
        white[i].add(i)

    ans = 0
    out = []
    for _ in range(Q):
        u, v = (int(x) - 1 for x in input().split())
        if ans == -1:
            out.append(-1)
            continue
        lu, lv = dsu.find(u), dsu.find(v)
        if lu == lv:
            if color[u] == color[v]:
                ans = -1
        else:
            ans -= min(len(white[lu]), len(black[lu]))
            ans -= min(len(white[lv]), len(black[lv]))
            if dsu.sz[lu] < dsu.sz[lv]:
                lu, lv = lv, lu
                u, v = v, u
            if color[u] == color[v]:
                white[lv], black[lv] = black[lv], white[lv]
                for x in white[lv]:
                    color[x] = 0
                for x in black[lv]:
                    color[x] = 1
            white[lu] |= white[lv]
            black[lu] |= black[lv]
            white[lv].clear()
            black[lv].clear()
            dsu.unite(lu, lv)
            ans += min(len(white[lu]), len(black[lu]))
        out.append(ans)
    print("\n".join(map(str, out)))

main()

复杂度分析

时间复杂度：均摊 $O((N + Q)\log N)$ （每个顶点因"所在分量大小翻倍"至多被翻转/移动 $O(\log N)$ 次；本实现基于 std::set，每个移动带一个 $\log N$ 因子，实际为 $O(N\log^2 N + Q\log N)$ ，仍能在时限内轻松通过）
空间复杂度： $O(N)$

G - Minimum XOR Walk

题目链接：https://atcoder.jp/contests/abc451/tasks/abc451_g

题目大意

给定一个 $N$ 个点、 $M$ 条边的简单连通无向图，每条边有权值 $W_i$ 。一条游走（walk） 的权定义为经过的所有边权的异或和（同一条边走多次就异或多次）。给定 $K$ ，求满足" $x$ 与 $y$ 之间所有游走的权的最小值 $\le K$ "的无序点对 $(x, y)$ 的数量。 $T$ 组测试数据， $\sum N, \sum M \le 2 \times 10^5$ ， $0 \le K < 2^{30}$ 。

思路

第一步：把所有游走权表示成"基向量异或"。 任取一棵生成树 $T$ ，设 $A_v$ 为树中 $1$ 到 $v$ 简单路径的异或和（ $A_1 = 0$ ）。对每条边 $e = (u, v)$ ，定义

W'_e = W_e \oplus A_u \oplus A_v.

由于树边满足 $A_u \oplus A_v = W_e$ ，树边的 $W'_e = 0$ 。任取一条游走 $v_1, v_2, \dots, v_k$ ，把每条边拆成 $W'_e \oplus A_{u} \oplus A_{v}$ ，中间顶点的 $A$ 恰好出现两次而被消去，只剩首尾：

\text{walk 权} = A_{v_1} \oplus W'_{e_1} \oplus W'_{e_2} \oplus \cdots \oplus W'_{e_{k-1}} \oplus A_{v_k}.

因为图连通，从 $x$ 出发可以任意绕行去走任何边，所以 $x$ 到 $y$ 的可达游走权集合为

\left\{ A_x \oplus A_y \oplus w \;\middle|\; w \in \operatorname{span}\{W'_e\} \right\},

其中 $\operatorname{span}$ 是异或意义下的线性张成（每个 $W'_e$ 可选 $0$ 或 $1$ 次）。

第二步：最小化。 定义

f(z) = \min_{w \in \operatorname{span}} (z \oplus w),

即 $f(z)$ 是 $z$ 所在陪集中的最小元素。则 $x, y$ 之间最小游走权为 $f(A_x \oplus A_y)$ 。

关键引理： $f(x \oplus y) = f(x) \oplus f(y)$ 。 证明概要：取 $\operatorname{span}$ 的一个"最高位互不相同"的线性基 $B$ 。由定义显然 $f(x\oplus y) \le f(x)\oplus f(y)$ 。若严格小于，则

f(x\oplus y) \oplus f(x) \oplus f(y) = b_1 \oplus \cdots \oplus b_k

是若干基向量的异或。设其中最高位（位于 $2^i$ 位）来自 $b$ 。由于 $f(x\oplus y) < f(x)\oplus f(y)$ ，二者在 $2^i$ 位分别为 $0$ 和 $1$ ，故 $f(x), f(y)$ 在 $2^i$ 位不同；不妨设 $f(x)$ 该位为 $1$ 。于是 $f(x) \oplus b < f(x)$ 且 $f(x) \oplus b \in F(x)$ ，与 $f(x)$ 是 $F(x)$ 中最小元素矛盾。故等号成立。

第三步：转化为线性基 + Trie 计数。 由引理，最小游走权

f(A_x \oplus A_y) = f(A_x) \oplus f(A_y).

令 $B_i = f(A_i)$ ，问题化为：统计满足 $B_i \oplus B_j \le K$ 的点对 $(i, j)$ 的数量。

计算 $f$ ：对 $\operatorname{span}\{W'_e\}$ 维护异或线性基， $f(x)$ 就是逐位用基"消去" $x$ 后得到的值，每次 $O(30)$ 。
计数：把所有 $B$ 按二进制位插入字典树（二进制 Trie）。对每个 $B_i$ ，统计已经插入的元素中有多少个 $y$ 满足 $(B_i \oplus y) \le K$ ：从高位向低位走，若 $K$ 当前位为 $1$ ，则把 $B_i$ 当前位相同的那棵子树全部计入（该位异或得 $0 < 1$ ），再走向异或位为 $1$ 的分支；若 $K$ 当前位为 $0$ ，则只能走向异或位为 $0$ 的分支。最后若一路走到底，还需加上"异或恰等于 $K$ "的部分。

总复杂度 $O((N + M) \cdot 30)$ 。

参考代码

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

struct Edge { int to; long long w; };

struct XorBasis {
    static const int L = 30;
    long long b[L];
    XorBasis() { memset(b, 0, sizeof b); }
    void insert(long long x) {
        for (int i = L - 1; i >= 0; --i) {
            if (((x >> i) & 1) == 0) continue;
            if (b[i] == 0) { b[i] = x; return; }
            x ^= b[i];
        }
    }
    // f(x) = min over span of (x xor w)
    long long reduce(long long x) const {
        for (int i = L - 1; i >= 0; --i)
            if ((x >> i) & 1) x ^= b[i];
        return x;
    }
};

struct TrieNode {
    int ch[2], cnt;
    TrieNode() { ch[0] = ch[1] = -1; cnt = 0; }
};

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

    int T;
    cin >> T;
    while (T--) {
        int N, M;
        long long K;
        cin >> N >> M >> K;

        vector<vector<Edge>> g(N + 1);
        vector<tuple<int, int, long long>> edges;
        for (int i = 0; i < M; ++i) {
            int u, v; long long w;
            cin >> u >> v >> w;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
            edges.push_back({u, v, w});
        }

        // BFS 求生成树路径异或和 A[v]
        vector<long long> A(N + 1, -1);
        vector<char> vis(N + 1, 0);
        queue<int> q;
        A[1] = 0; vis[1] = 1; q.push(1);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &e : g[u]) {
                if (!vis[e.to]) {
                    vis[e.to] = 1;
                    A[e.to] = A[u] ^ e.w;
                    q.push(e.to);
                }
            }
        }

        // 建异或线性基（树边的 W' = 0，插入无影响）
        XorBasis basis;
        for (auto [u, v, w] : edges) basis.insert(w ^ A[u] ^ A[v]);

        vector<long long> B(N + 1);
        for (int i = 1; i <= N; ++i) B[i] = basis.reduce(A[i]);

        // 二进制 Trie：统计 B_i xor B_j <= K 的点对
        vector<TrieNode> trie;
        trie.reserve((long long)N * 31 + 1);
        trie.push_back(TrieNode());

        auto insert = [&](long long x) {
            int node = 0;
            for (int bit = 29; bit >= 0; --bit) {
                int b = (x >> bit) & 1;
                if (trie[node].ch[b] == -1) {
                    trie[node].ch[b] = (int)trie.size();
                    trie.push_back(TrieNode());
                }
                node = trie[node].ch[b];
                trie[node].cnt++;
            }
        };
        auto countLE = [&](long long x) {
            // 统计 trie 中满足 (x xor y) <= K 的元素个数
            long long res = 0;
            int node = 0;
            for (int bit = 29; bit >= 0; --bit) {
                int xb = (x >> bit) & 1;
                int kb = (K >> bit) & 1;
                if (kb == 1) {
                    int nb = trie[node].ch[xb];          // 异或位为 0 < 1，全部计入
                    if (nb != -1) res += trie[nb].cnt;
                    node = trie[node].ch[xb ^ 1];        // 继续沿异或位为 1 的分支
                } else {
                    node = trie[node].ch[xb];            // 异或位必须为 0
                }
                if (node == -1) break;
            }
            if (node != -1) res += trie[node].cnt;       // 异或恰等于 K
            return res;
        };

        long long ans = 0;
        for (int i = 1; i <= N; ++i) {
            ans += countLE(B[i]);   // 与已插入的 j < i 配对
            insert(B[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O((N + M) \cdot 30)$ （线性基建立与 $f$ 的化简均为每元素 $O(30)$ ，Trie 插入/查询每个元素 $O(30)$ ）
空间复杂度： $O(N \cdot 30)$ （Trie 节点；线性基、邻接表均为 $O(N + M)$ ）