https://atcoder.jp/contests/abc408/tasks/abc408_e
あり得る最大値から考えてみる。
ある辺を通っていくと 1<<30 - 1 ていう答えになるかもしれない。
けど別の辺を選んで通るとどこか1bit削減できる。みたいなことを考える。
特定の1bit を使わずに1→N までいけるかっていう判定問題を考える。
最上位bit(LSBから29bit目) 使わずに行けるルートがあるならば、そのルートを絶対に採用するべき。
最上位bitを使わず、さらに28bit目を使わずにいけるルートがあるなば…
最上位bit 28bit 27bit目を使わずに…
っていうふうに上位bitから使わずにいけるルートがあるか調べる(これはunion findで簡単に実装できる)
いけないbitを 1<<30-1から弾いた値が答え。
またこれは上位bitから調べないといけない。
感覚的に言うならばMSBとLSBどちらか一つだけ消せるとなったときにMSB消さないと答えの寄与としてもったいない。