ABC201-E Xor Distances

本番で解けず。重みを桁ごとに分解するという発想がなかった

【問題】

重み付き木が与えられる。

dist(i, j) = iからjへの最短パスに含まれる辺すべての重みのXOR

すべてのi ,j(i<j)についてdistの総和を求めよ

【忘れがちな知識】

総和は桁ごとに独立して足し合わせられる

例：123+789 = 1*10^2+7*10^2+2*10^1+8*10^1+3^10^0+9*10^0

【典型ポイント】

XOR => 桁ごとに考える

【方針】

愚直にdist(i,j)を全列挙としようとすると最低でもO(N^2)となり、全然間に合わない。

また、それぞれのdist(i, j)も高速に求める必要がある。

・2点間の最短パスを高速に求める

適当な根をrとして木を探索し、dist(r, i)を求める。

jこのとき、dist(i, j) = dist(r, i) ^ dist(r, j) となる(下図参照)

ので、任意のdist(i, j)を前計算O(N), 処理O(1)で求められる。

これで各distを高速に求めることはできたが、まだO(N^2)かかる。

・distを桁ごとに求める

dist(i, j)はXOR演算を繰り返すので、桁ごとに独立して考えることができる。

 こうすると辺の重みとdist(i, j)の各桁は0か1の2通りになる。

各桁のdist(i, j)をdk(i, j)とすると

任意のi, j(i<j)を選んだ時、dk(i, j)が1になるのはdk(r,i) != dk(r, j)のときなので、

dk(i, j) = 1 と dk(r, i) != dk(r, j) が等しい。

よって、各桁においてdist(i, j) = 1 となる組み合わせの数は、1~nの各頂点において

count(dk=0) * count(dk=1) 

となる。(2種類のボールの山から2個を選んだ時に色が異なる組み合わせの数と同じ)