No.045 C

木を頂点 $1$ を根とする根付き木とする. 頂点 $i, j$ 間の xor 和を $S(i, j)$ とする.

ここで, 任意の頂点 $a, b$ について $S(a, b)$ を考える. $a, b$ の LCA を $c$ とすると,

$$\begin{align} S(a, b) &= S(a, c) \oplus S(b, c) \\ &= S(a, c) \oplus S(b, c) \oplus (S(1, c) \oplus S(1, c)) \\ &= (S(a, c) \oplus S(1, c)) \oplus (S(b, c) \oplus S(1, c)) \\ &= S(1, a) \oplus S(1, b) \end{align}$$

となる. $S(1, i)$ は幅優先探索であらかじめ計算しておくことができる.

あとは頂点ごとに, $S(1, i) \oplus X = S(1, j)$ となる $j$ の数を数える. これは $S(1, j)$ をソートしておけば二分探索で求められる. (ただし, $X=0$ のときは自身の頂点を含めて数えてしまうのでこの分は引いておく)

上記の数え方では $(a, b), (b, a)$ をダブルカウントしているので, 最後に2で割る.