公式解説と同じになってしまいましたが,せっかく書いたので公開します.
問題はこちら
問題概要
頂点の木の任意の頂点についての総和を求めよ.ただし,とはからへの最短パスに含まれる辺全ての重みのXORと定める.解説
もちろんをいちいち計算していたらかかるので間に合わない.XORは進法で桁ごとの演算であるので,ここでも桁ごとに考える.下から桁目のみについて考えると,すべての辺の重みがかである木になり,この問題の答えをとすると元の問題の答えはとなる.
入力例での例:,
以下,すべての辺の重みがかである木についての問題を解く.
この木をある頂点を根とする根付き木として見る.各頂点についてをDFSなどを用いて計算すると,任意のについてとなる(はXOR).はかであるので,がとなるようなの数を数えられればいい.つまり,となるの数が知りたい.これは,となるの数ととなるの数を持ちながらDFSすればよい.