https://kanpurin.hatenablog.com/entry/2021/05/15/224226

公式解説と同じになってしまいましたが，せっかく書いたので公開します．

問題概要

${N}$ 頂点の木の任意の ${2}$ 頂点 ${1\leq i < j\leq N}$ について ${dist(i,j)}$ の総和を求めよ．ただし， ${dist(i,j)}$ とは ${i}$ から ${j}$ への最短パスに含まれる辺全ての重み ${w}$ のXORと定める．

${2\leq N\leq 2×10^5\\ 0\leq w_{i,j} < 2^{60}}$

解説

もちろん ${dist(i,j)}$ をいちいち計算していたら ${O(N^2)}$ かかるので間に合わない．

XORは ${2}$ 進法で桁ごとの演算であるので，ここでも桁ごとに考える．下から ${k}$ 桁目のみについて考えると，すべての辺の重みが ${0}$ か ${1}$ である木になり，この問題の答えを ${ans_k}$ とすると元の問題の答えは ${\displaystyle\sum_{k=1}^{60}ans_k×2^{k-1}}$ となる．

入力例 ${1}$ での例： ${1=01_{(2)}}$ ， ${3=11_{(2)}}$

f:id:kanpurin:20210515223509p:plain:w500

以下，すべての辺の重みが ${0}$ か ${1}$ である木についての問題を解く．
この木をある頂点 ${r}$ を根とする根付き木として見る．各頂点 ${i}$ について ${dist(r,i)}$ をDFSなどを用いて計算すると，任意の ${i,j}$ について ${dist(i,j)=dist(r,i)\oplus dist(r,j)}$ となる( ${\oplus}$ はXOR)． ${dist(i,j)}$ は ${0}$ か ${1}$ であるので， ${dist(i,j)}$ が ${1}$ となるような ${(i,j)}$ の数を数えられればいい．つまり， ${dist(r,i)\neq dist(r,j)}$ となる ${(i,j)}$ の数が知りたい．これは， ${dist(r,i)=0}$ となる ${i}$ の数と ${dist(r,i)=1}$ となる ${i}$ の数を持ちながらDFSすればよい．

提出プログラム

https://atcoder.jp/contests/abc201/submissions/22635722

感想

XORは桁ごとに考えるのは典型です．