解法 1

仮想的な頂点 \(v\) を作り、重み \(0\) の辺を用いて木のいずれかの頂点に接続しましょう（操作はこの辺にも影響しますが、この辺に対して操作を行うことはありません）。\(2\) 頂点 \(a, b\) 間の 距離 \(dist(a, b)\) を、それらを結ぶ一意なパス上の辺全ての重みの XOR と定義します。

\(v\) から他の全ての頂点への距離を観察しましょう。辺 \((a, b)\) に対して操作を行うと、\(dist(v, a)\) と \(dist(v, b)\) が入れ替わり、この他の距離には変化がないことが簡単に分かります。

これにより、問題は次のようになります。「頂点 \(v\) からの辺の重みの目標値 \(W\) であって、グラフの最終状態における \(v\) から他の頂点への距離が、グラフの初期状態における \(v\) から他の頂点への距離を並べ替えたものになるようなものは存在するか。」これは、次の問題と同値です。

「\(2\) つの数列 \((a_1, a_2, \dots a_n)\) と \((b_1, b_2, \dots, b_n)\) がある。(\(W\) XOR \(b_1\), \(\dots\), \(W\) XOR \(b_n\)) が \((a_1, a_2, \dots, a_n)\) の並べ替えになっているような \(W\) は存在するか。」

\(n\) が奇数であることから、\(W\) を \(a_1\) XOR \(a_2\) \(\dots\) XOR \(a_n\) XOR \(b_1\) \(\dots\) XOR \(b_n\) として簡単に求めることができることに注目します。あとは、一方の数列にこの値を XOR することでもう一方の数列の並べ替えとなるかを確認するのみです。

合計計算量: \(O(N\log{N})\)

解法 2

木に対して、以下の条件を満たすような頂点への数の割り当て \(f(v)\) を求めましょう。

• 各辺 $(u, v)$ に対し、その重みを $w$ として $f(u)$ XOR $f(v) = w$
• $f(1)$ XOR $f(2)$ XOR $f(n) = 0$

\(n\) が奇数であることから、このような割り当ては一意に定まります。辺 \((u, v)\) に対する操作が \(f(u), f(v)\) を入れ替えるのみであることに注目すると、この割り当てを \(2\) つの木に対して求め、一方がもう一方の並べ替えとなっているかを確認すれば答えを得られます。

合計計算量: \(O(N\log{N})\)