かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC201 E - Xor Distances

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

問題はこちら

問題概要

{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は桁ごとに考えるのは典型です.