BFS做法

#include<bits/stdc++.h>

using namespace std;
map<int, map<int, int>> graph;
map<int, map<int, bool>> vis;
struct Node{
    int x, value;
    bool isPool;
};
int n, a, b;

void bfs(){
    queue<Node> que;
    que.push(Node{a, 0, true});
    while(!que.empty()){
        auto &head=que.front();
        if(head.x==b){
            que.pop();
            continue;
        }
        for(auto i:graph[head.x]){
            int value=head.value ^ i.second;
            if(i.first == b){
                if(value == 0){
                    printf("YES\n");
                    return;
                }
                continue;
            }
            if(!vis[i.first][value]){
                vis[i.first][value]=true;
                que.push(Node{i.first, value, head.isPool});
            }
        }
        if(head.isPool){
            for(int i=1;i <= n;i++){
                if(i != b){
                    if(!vis[i][head.value]){
                        vis[i][head.value]=true;
                        que.push(Node{i,head.value, false});
                    }
                }
            }
        }
        que.pop();
    }
    printf("NO\n");
}

void f(){
    graph.clear();
    vis.clear();
    scanf("%d%d%d", &n, &a, &b);
    for(int i=1;i <= n-1;i++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        graph[x][y]=z;
        graph[y][x]=z;
    }
    bfs();
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        f();
    }
    return 0;
}