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])が解