排他的論理和(XOR)に関する問題 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</j)についてdistの総和を求めよ>…