解説

数列上のペアの XOR の最大値に変換する

まず、木そのままではパスの XOR の最大というものを考えるのが面倒です。そこで、オイラーツアーを使って、木を列に切り開いてしまいます。 どのような木に対しても、パス上の XOR は、その木のオイラーツアーのいずれかの区間上の XOR と等しくなります。

オイラーツアー上の累積 XOR を取ることで、元の木でのパス上の XOR は、累積 XOR を取った数列上のペアの XOR となります。

数列上のペアの XOR の最大値を求める

参考: Maximum XOR of Two Numbers in an Array - GeeksforGeeks

上位のビットから順に確定させていくことで答えが求まります。まず、今 $i$ 番目よりも上のビットより上が答えと等しく、 $i$ ビット目が $1$ 、それよりも下のビットがすべて $0$ となるような数 $a$ を考えます。このとき、 $a \gg i = (x \oplus y) \gg i$ となるようなペア $(x, y)$ が数列に存在するなら、答えの $i$ ビット目は $1$ 、そうでなければ $0$ となります。

実装例

Ruby での実装になります。 DFS を再帰ですると遅いため、スタックでしました。