Codeforces #396 Div. 2 E: Mahmoud and a xor trip

とりあえず1を根とする根付き木として考える。

f[i][j][k] := 頂点iについて、頂点iの子孫のうち、iからその子孫までのパスの距離のjビット目がkであるような子孫の数

とする。これをメモ化再帰で解く。

ある頂点uについて

uが最も根に近い頂点であるようなパスは、uと子孫との関係から3パターンがある。

つまりvとwをuの子孫として(u,v,wはすべて異なる)

(1) v <=> u<=> w

(2) u <=> v

(3) u

これらを

f[u][j][k]を計算しながら、uが最も根に近い頂点であるようなパスの距離の和g[u]を求める。Σ(g[u])が解