G. SlavicG's Favorite Problem - 题解

比赛与标签

比赛: Codeforces Round 835 (Div. 4) 标签: bitmasks, dfs and similar, graphs 难度: *1700

题目大意喵~

主人，我们来玩一个在树上的小游戏吧！

我们有一棵带权重的树，还有一个初始为0的变量x。我们要从起点a走到终点b。每当我们走过一条权重为w的边，变量x的值就会变成 x XOR w（XOR是按位异或操作哦）。

游戏的胜利条件有点特别：只有当我们的x值在经过某条边(u, b)后恰好变为0时，我们才能进入终点b。也就是说，在节点u时，必须满足 当前的x XOR 边(u,b)的权重 = 0。

更有趣的是，我们还有一个超能力：在整个旅途中，我们可以随时随地进行最多一次传送，可以从任意节点传送到除了b以外的任意一个节点。

我们的任务就是判断，是否存在一种合法的走法（可以传送也可以不传送），能让我们从a成功到达b呢？如果可以就输出"YES"，不行就"NO"啦，喵~

解题思路喵~

主人，这个问题看起来有点绕，但别怕，让本喵来帮你梳理一下思路吧！我们可以把问题分解成两种情况来考虑：不使用传送和使用一次传送。

情况一：不使用传送，直接走过去！

这是最简单的情况啦！如果我们不使用传送，那么从a到b的路径在树上是唯一确定的。

我们来分析一下胜利条件：假设我们到达b前的最后一个节点是u，边(u, b)的权重是w_ub。此时，我们从a走到u的路径上所有边权的异或和就是我们当前的x值，我们称之为path_xor(a, u)。胜利条件是 path_xor(a, u) XOR w_ub = 0。

嘿嘿，主人你看，path_xor(a, u) XOR w_ub其实就是从a到b整条路径的异或和path_xor(a, b)呀！所以，不使用传送就能获胜的条件，就等价于从a到b的唯一路径的边权异或和为0。

这个path_xor(a, b)很好求的！我们只要从a点开始做一次图的遍历（比如BFS或者DFS），就能计算出a到所有其他点的路径异或和啦。

情况二：使用一次宝贵的传送机会！

如果直接走不通，我们就得动用我们的超能力——传送！

一次传送的旅程是这样的：

从起点a出发，经过一条路径到达某个节点u。这条路径不能经过b哦，因为一旦到了b游戏就结束了。
在节点u，我们发动传送！咻~一下，我们被传送到了某个节点v（注意，v不能是b）。传送本身不改变x的值。
此时，我们身在v，而变量x的值等于path_xor(a, u)。
接着，我们从v出发，沿着树上的路径走向终点b。
最终，要进入b，必须满足：(在v点时的x值) XOR (从v到b的路径异或和) = 0。

把上面的公式写出来就是：path_xor(a, u) XOR path_xor(v, b) = 0。根据XOR的奇妙性质（A XOR B = 0 当且仅当 A = B），这个条件等价于： path_xor(a, u) = path_xor(v, b)

这给了我们一个绝妙的“相遇”策略！

我们需要找到一个可以从a到达的、不是b的节点u。
我们还需要找到一个可以作为传送目的地的、不是b的节点v。
并且它们满足 path_xor(a, u) 等于 path_xor(v, b)。

所以，我们的解法就清晰了喵~：

第一步：先处理最简单的情况。从a开始做一次BFS，计算a到所有点的路径异或和。如果path_xor(a, b) == 0，太棒了，直接输出"YES"！
第二步：如果直接走不行，我们就准备“相遇”。
- A部分：我们从a开始做一次BFS，但这次有一个限制：不能访问节点b。我们把所有能到达的节点u的path_xor(a, u)收集起来，放进一个集合 SetA。SetA代表了我们传送前可能拥有的所有x值。
- B部分：我们再从b开始做一次BFS，计算b到所有其他节点的路径异或和path_xor(b, v)。因为path_xor(v, b) = path_xor(b, v)，所以这就是我们需要的从v到b的路径异或和。我们把所有v != b的节点的path_xor(b, v)收集起来，放进另一个集合 SetB。
第三步：检查SetA和SetB是否有共同的元素。如果存在一个值val，它既在SetA里又在SetB里，那就意味着我们可以找到一个u和一个v，使得path_xor(a, u) = val并且path_xor(v, b) = val。这样，val XOR val = 0，胜利条件达成！输出"YES"。

如果检查完所有可能，SetA和SetB都没有交集，那就说明真的没办法了，只能遗憾地输出"NO"了。

代码实现喵！

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

// 主函数入口喵~
int main() {
    // 加速输入输出，让程序跑得飞快！
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t; // 有t组测试数据呢
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b; // 节点数，起点a，终点b

        // 用邻接表来存这棵树，pair里是邻接点和边权
        vector<vector<pair<int, long long>>> graph(n + 1);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            long long w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }

        // --- 情况一：检查不使用传送 ---
        // dist_full[i] 存储从 a 到 i 的路径异或和
        vector<long long> dist_full(n + 1, -1);
        queue<int> q;
        dist_full[a] = 0; // a到a自己，当然是0啦
        q.push(a);

        // 一个标准的BFS，用来计算路径异或和
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto [v, w] : graph[u]) {
                if (dist_full[v] == -1) { // 如果v还没被访问过
                    dist_full[v] = dist_full[u] ^ w;
                    q.push(v);
                }
            }
        }

        // 如果a到b的路径异或和直接就是0，那么我们赢了！
        if (dist_full[b] == 0) {
            cout << "YES\n";
            continue; // 处理下一组数据
        }

        // --- 情况二：使用一次传送 ---
        // S集合：存储从a出发、不经过b，能到达的所有点的路径异或和
        vector<long long> distA(n + 1, -1);
        set<long long> S;
        queue<int> q1;

        distA[a] = 0;
        q1.push(a);
        S.insert(0); // a点本身，路径异或和为0

        // BFS from 'a', but avoiding 'b'
        while (!q1.empty()) {
            int u = q1.front();
            q1.pop();
            for (auto [v, w] : graph[u]) {
                if (v == b) continue; // 不准去b点！
                if (distA[v] == -1) {
                    distA[v] = distA[u] ^ w;
                    S.insert(distA[v]);
                    q1.push(v);
                }
            }
        }

        // T集合：存储从b出发，到所有其他点的路径异或和
        vector<long long> distB(n + 1, -1);
        set<long long> T;
        queue<int> q2;

        distB[b] = 0;
        q2.push(b);

        // BFS from 'b'
        while (!q2.empty()) {
            int u = q2.front();
            q2.pop();
            // 传送目的地不能是b，所以不把b到b的路径和(0)加入T
            if (u != b) { 
                T.insert(distB[u]);
            }
            for (auto [v, w] : graph[u]) {
                if (distB[v] == -1) {
                    distB[v] = distB[u] ^ w;
                    q2.push(v);
                }
            }
        }

        // 检查两个集合是否有交集
        bool found = false;
        for (long long x : S) {
            if (T.count(x)) { // 如果在T中找到了S中的元素
                found = true;
                break; // 找到一个就够啦！
            }
        }

        cout << (found ? "YES" : "NO") << '\n';
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。我们主要进行了三次BFS。在树上，BFS的时间复杂度是O(N+M)，其中N是顶点数，M是边数。因为是树，所以M = N-1，所以每次BFS是O(N)的。之后，我们遍历集合S（大小最多为N），并在集合T（大小也最多为N）中查找。std::set的查找操作是O(log N)的。所以这部分的复杂度是O(N log N)。总的时间复杂度就是 O(N + N + N + N log N) = O(N log N)。对于题目给的数据范围，完全没问题！
空间复杂度: O(N) 的说。我们用了邻接表graph来存图，空间是O(N)。几个dist数组也是O(N)。两个集合S和T在最坏情况下可能存N个元素，所以也是O(N)。总的空间复杂度就是O(N)啦。

知识点与总结喵~

这道题真是一次愉快的冒险！它教会了我们好几个重要的知识点呢：

XOR的性质: a ^ a = 0 和 a ^ b = c 等价于 a ^ c = b。这是解开谜题的关键钥匙！利用这个性质，我们才能把复杂的胜利条件转化为简单的等式。
图的遍历 (BFS): BFS是解决图路径问题的强大工具。在这里，我们用它来高效地计算从某个源点到所有其他点的路径异或和。
问题分解: 将一个复杂问题（传送+行走）分解成几个更简单、更清晰的子问题（不传送、传送），是算法解题中非常重要的思想。
“相遇”思想: 虽然不是严格的“双向搜索”或“中间相遇攻击”，但这种“分别从起点和终点出发，收集可能性，再看有无交集”的思路非常有效，可以解决很多看似棘手的问题。

希望本喵的讲解能帮助到主人！只要把问题分解成几个小部分，一步一步来，就没那么可怕啦！主人下次遇到类似的题目也一定能解决的，加油喵~！

G. SlavicG's Favorite Problem - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

情况一：不使用传送，直接走过去！ ​

情况二：使用一次宝贵的传送机会！ ​

代码实现喵！ ​

复杂度分析的说 ​

知识点与总结喵~ ​