解説

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

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

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

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

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

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

実装例

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