Solution 1

Let’s create fictional node \(v\) and connect it to any node of the tree with an edge of weight \(0\) (operations will affect this edge as well, but we won’t perform operation with it). Let’s define the distance \(dist(a, b)\) between \(2\) nodes \(a\) and \(b\) as XOR of all weights on the unique path between them in the tree.

Let’s look at distances from \(v\) to all other nodes of the tree. It can easily be seen that if we perform operation on edge \((a, b)\), then \(dist(v, a)\) and \(dist(v, b)\) swap, and all other distances remain the same.

Now the question is: is there such goal weight of edge from node \(v\) - \(W\), such that distances from \(v\) to other nodes in the final graph will be a permutation of distances from v to other nodes in the initial graph? This is equivalent to the following question:

We have \(2\) arrays \((a_1, a_2, \dots a_n)\) and \((b_1, b_2, \dots, b_n)\), and have to determine if there is such \(W\) such that (\(W\) XOR \(b_1\), \(\dots\), \(W\) XOR \(b_n\)) is a permutation of \((a_1, a_2, \dots, a_n)\).

Note that as \(n\) is odd, \(W\) is easily deducible as \(a_1\) XOR \(a_2\) \(\dots\) XOR \(a_n\) XOR \(b_1\) \(\dots\) XOR \(b_n\). So we just check if after XORing one array is a permutation of other.

Total asymptotics \(O(N\log{N})\).

Solution 2

For a tree, let’s find an assignment \(f(v)\) of numbers to the nodes satisfying:

• For every edge $(u, v)$ with weight $w$, $f(u)$ XOR $f(v) = w$
• $f(1)$ XOR $f(2)$ XOR $\dots$ XOR $f(n) = 0$

As \(n\) is odd, this assignment is unique. Note that the operation on edge \((u, v)\) just swaps \(f(u), f(v)\). So find this assignment on both trees and check if one is a permutation of another.

Total asymptotics \(O(N\log{N})\).