ABC126D Even Relation

わからねぇ〜〜〜!!!

D - Even Relation

考え方

  • 二点の距離を求める場合、どこかの点を根として根付き木として考えると良さそう。

また、ある点を根として、点$a$と点$b$の最小共通祖先を点$w$として、根から点$i$の距離を $d[i]$とすると、点$a$と点$b$の距離は$d[a]+d[b]-2*d[w]$で求めることができる!

よっしゃLCA求めたろっ!ってなるが、もう一歩考える必要がある。

LCAを求めるのも良いが、めっちゃ大変。

ここで、もう少し考えると、 $-2*d[w]$は明らかに偶数である。

で、そうなると、d[a]+d[b]の偶奇を考えれば良い問題になる。

d[a]とd[b]の偶奇が等しければaとbとの距離は偶数になる。

よって、d[a]が偶数なら白、奇数なら黒といった様に塗れば良い。

根付き木ちゃんと書いたことなくて無限にバグらせた。

提出 #11240771 - AtCoder Beginner Contest 126

Share on: