AtCoder Regular Contest 045 C - エックスオア多橋君
問題概要
- 木
- ノードとノードの単純パスの距離は通ったエッジのXOR和
- XOR和がXになるのは何通りか
解法
あるノードを根とした時、aとbの単純パスはa-LCA(a,b)-bである。
※LCAはLowest Common Ancestor
すなわちその距離L(a,b)は、
L(a,b) = L(a,LCA(a,b))^L(LCA(a,b),b)
ここで、
A^X^X = A
であることを考えると
L(a,b) = L(a,LCA(a,b))^L(LCA(a,b),b)
= L(a,LCA(a,b))^L(LCA(a,b),root)^L(root,LCA(a,b))^L(LCA(a,b),b) ※rootは根
= L(a,root)^L(root,B)
である。
つまり、a-root-bと辿った場合に等しい。
したがって、適当なノードを根とし、全探索で距離を求めたあと、a-root-bの距離がXとなる組み合わせを数えればよい。