競技プログラミングノート

競技プログラミングで解いた問題を記録するだけ

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となる組み合わせを数えればよい。