G - SlavicG's Favorite Problem.cpp

#include <bits/stdc++.h>

using namespace std;

const int MX = 1e5 + 5;

int t, n, a, b;
vector <pair<int, int> > adj[MX];

void DFS(int par, int pos, vector <int> &v, bool flag){
    for(auto p : adj[pos]){
        int nxt = p.first;
        int w = p.second;
        if(flag && nxt == b) continue;
        if(nxt == par) continue;

        v[nxt] = v[pos] ^ w;
        DFS(pos, nxt, v, flag);
    }
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    cin >> t;
    while(t--){
        cin >> n >> a >> b;
        a--, b--;
        for(int i = 1; i < n; i++){
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }

        vector <int> v1(n, 0), v2(n, 0);

        DFS(-1, a, v1, true), DFS(-1, b, v2, false);
        v1[b] = -100, v2[b] = -1000;
        sort(v2.begin(), v2.end());

        bool ans = false;
        for(int i : v1){
            auto it = lower_bound(v2.begin(), v2.end(), i);
            if(it != v2.end() && (*it) == i) ans = true;
        }

        for(int i = 0; i < n; i++) adj[i].clear();

        cout << (ans ? "YES\n" : "NO\n");
    }
}