P4551 Longest XOR Path

Given a weighted tree with $n$ nodes, indexed from $1$ to $n$. Find the maximum value among the XOR of all paths in the tree. An XOR path is the XOR of all edge weights along the unique path between two nodes in the tree. Constraints $1 \le n \le 10^5; 0 < u, v \le n; 0 \le w < 2^{31}$.

The first line contains an integer $n$, the number of nodes. The next $n-1$ lines each contain $u, v, w$, meaning there is an edge between node $u$ and node $v$ with weight $w$.

One line with a single integer, the answer.

When the two nodes are $1$ and $3$, the value is $7=3\oplus 4$, which is the maximum. Translated by ChatGPT 5