parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ とりあえず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])が解 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F02%2F09%2F150410" title="Codeforces #396 Div. 2 E: Mahmoud and a xor trip - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-02-09 15:04:10 rich https://par.hateblo.jp/entry/2017/02/09/150410 1.0 100%