SlavicG's Favorite Problem (Codeforces 1760G)
Tags: Others, graphs

You are given a weighted tree with $$$n$$$ vertices. Recall that a tree is a connected graph without any cycles. A weighted tree is a tree in which each edge has a certain weight. The tree is undirected, it doesn't have a root.Since trees bore you, you decided to challenge yourself and play a game on the given tree.In a move, you can travel from a node to one of its neighbors (another node it has a direct edge with).You start with a variable $$$x$$$ which is initially equal to $$$0$$$. When you pass through edge $$$i$$$, $$$x$$$ changes its value to $$$x ~\mathsf{XOR}~ w_i$$$ (where $$$w_i$$$ is the weight of the $$$i$$$-th edge). Your task is to go from vertex $$$a$$$ to vertex $$$b$$$, but you are allowed to enter node $$$b$$$ if and only if after traveling to it, the value of $$$x$$$ will become $$$0$$$. In other words, you can travel to node $$$b$$$ only by using an edge $$$i$$$ such that $$$x ~\mathsf{XOR}~ w_i = 0$$$. Once you enter node $$$b$$$ the game ends and you win.Additionally, you can teleport at most once at any point in time to any vertex except vertex $$$b$$$. You can teleport from any vertex, even from $$$a$$$.Answer with "YES" if you can reach vertex $$$b$$$ from $$$a$$$, and "NO" otherwise.Note that $$$\mathsf{XOR}$$$ represents the bitwise XOR operation.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$2 \leq n \leq 10^5$$$), ($$$1 \leq a, b \leq n; a \ne b$$$) — the number of vertices, and the starting and desired ending node respectively.Each of the next $$$n-1$$$ lines denotes an edge of the tree. Edge $$$i$$$ is denoted by three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$  — the labels of vertices it connects ($$$1 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 10^9$$$) and the weight of the respective edge.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case output "YES" if you can reach vertex $$$b$$$, and "NO" otherwise.

Note: For the first test case, we can travel from node $$$1$$$ to node $$$3$$$, $$$x$$$ changing from $$$0$$$ to $$$1$$$, then we travel from node $$$3$$$ to node $$$2$$$, $$$x$$$ becoming equal to $$$3$$$. Now, we can teleport to node $$$3$$$ and travel from node $$$3$$$ to node $$$4$$$, reaching node $$$b$$$, since $$$x$$$ became equal to $$$0$$$ in the end, so we should answer "YES".For the second test case, we have no moves, since we can't teleport to node $$$b$$$ and the only move we have is to travel to node $$$2$$$ which is impossible since $$$x$$$ wouldn't be equal to $$$0$$$ when reaching it, so we should answer "NO".

Sample Inputs:
3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5

Sample Outputs:
YES
NO
YES

Solution (Python):
import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
input = sys.stdin.readline
stack = []
startset = set()
res = []
t = int(input())
for _ in range(t):
    (n, st, fi) = map(int, input().split())
    g = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (a, b, w) = map(int, input().split())
        g[a].append((b, w))
        g[b].append((a, w))
    startset.clear()
    used = [False] * (n + 1)
    used[fi] = True
    stack.append((st, 0))
    while stack:
        (v, wei) = stack.pop()
        used[v] = True
        startset.add(wei)
        for (n_node, w) in g[v]:
            if not used[n_node]:
                stack.append((n_node, wei ^ w))
    used = [False] * (n + 1)
    stack.append((fi, 0))
    found = False
    while stack:
        (v, wei) = stack.pop()
        used[v] = True
        if v != fi and wei in startset:
            stack.clear()
            found = True
            break
        for (n_node, w) in g[v]:
            if not used[n_node]:
                stack.append((n_node, wei ^ w))
    res.append('YES' if found else 'NO')
print(*res, sep='\n')

Solution (Python):
import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
input = sys.stdin.readline
stack = []
startset = set()
res = []
t = int(input())
for _ in range(t):
    (n, st, fi) = map(int, input().split())
    g = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (a, b, w) = map(int, input().split())
        g[a].append((b, w))
        g[b].append((a, w))
    startset.clear()
    used = [False] * (n + 1)
    used[fi] = True
    stack.append((st, 0))
    while stack:
        (v, wei) = stack.pop()
        used[v] = True
        startset.add(wei)
        for (n_node, w) in g[v]:
            if not used[n_node]:
                stack.append((n_node, wei ^ w))
    used = [False] * (n + 1)
    stack.append((fi, 0))
    found = False
    while stack:
        (v, wei) = stack.pop()
        used[v] = True
        if v != fi and wei in startset:
            stack.clear()
            found = True
            break
        for (n_node, w) in g[v]:
            if not used[n_node]:
                stack.append((n_node, wei ^ w))
    res.append('YES' if found else 'NO')
print(*res, sep='\n')

Solution (Python):
stack = []
s = set()
for _ in range(int(input())):
    (n, a, b) = map(int, input().split())
    a -= 1
    b -= 1
    gra = [[] for i in range(n)]
    for i in range(n - 1):
        (u, v, w) = map(int, input().split())
        u -= 1
        v -= 1
        gra[u].append((v, w))
        gra[v].append((u, w))
    s.clear()
    used = [False] * n
    used[b] = True
    stack.append((a, 0))
    while stack:
        (ver, h) = stack.pop()
        used[ver] = True
        s.add(h)
        for (t, w) in gra[ver]:
            if not used[t]:
                stack.append((t, w ^ h))
    used = [False] * n
    stack.append((b, 0))
    found = False
    while stack:
        (ver, h) = stack.pop()
        used[ver] = True
        if ver != b and h in s:
            stack.clear()
            found = True
            break
        for (t, w) in gra[ver]:
            if not used[t]:
                stack.append((t, w ^ h))
    print('YES' if found else 'NO')