パターンが同じになるものを見つけて、まとめて計算する。
$D=1$ の場合、答えは辺数×2 $=2^{N+1}-4$ となる。
以下、$D \ge 2$ とする。
完全二分木なので、深さが同じ頂点以下の部分木は形状が全く一緒となる。
当然、その中だけで取れる答えの対象ペアの個数も一緒となる。
一方、深さが異なる頂点の部分木同士はまとめて考えることはできないため、深さでグループ分けするのがよさそう。
深さ $d$ に位置する頂点($v$ とする)毎に、
「$v$ が2頂点を結ぶパスに含まれ、かつそれが最も浅い頂点である」組の個数を数えると、重複せずに数え上げられる。
以下の2つに分けて考える。
N=5 d ① 0 ,-----' `-----, ② ③ 1 / \ / \ ④ ⑤ ⑥ ⑦ 2 /\ /\ /\ /\ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬ ⑭ ⑮ 3 /\ /\ /\ /\ /\ /\ /\ /\ ⑯⑰⑱⑲⑳㉑㉒㉓㉔㉕㉖㉗㉘㉙㉚㉛ 4
上記の例で、例えば $D=3$ のとき、②にとっての (②,⑯), (②,㉒) などが該当する。
$d+D \ge N$ なら、$D$ だけ深い頂点は存在しない。
$d+D \lt N$ の場合、1頂点につき $2^D$ のペア対象が存在する。(②に対する⑯~㉓)
今回の問題では $(i,j),(j,i)$ は別に数えるので2倍、さらに深さ $d$ には $2^d$ 個の頂点があるので、
全部で $2^{d+D+1}$ となる。
上記の例で、例えば $D=3$ のとき、②にとっての (⑧,⑤), (④,⑪) などが該当する。
左の頂点を深さ $d+l$ の頂点とすると、距離 $D$ にするためには右は深さ $d+(D-l)$ となる。
②にとって、自身より $l$ 深い左の頂点は $2^{l-1}$ 個、$D-l$ 深い右の頂点は $2^{D-l-1}$ 個で、 この組合せは $2^{D-2}$ 個となる。
つまり、$l$ に関わらず、どの深さとどの深さをペアにしても組合せは常に $2^{D-2}$ で固定である。いい感じ。
では何通りの $l$ が取れるのかだが、
この2つの小さい方が、$l$ が取れるパターン数($p$ とする)となる。
A.と同様、反転させたペアで2倍、深さ $d$ には $2^d$ 個の頂点があるので、
全部で $p \times 2^{d+D-1}$ となる。
$d=0~N-2$ まで足し合わせた結果が答え。
主客転倒で考える。
1本の辺が、どの頂点にどれだけ寄与するのか考える。
... ○--, e ,--○ ○-○---○-○-○ ... ○----' `--○ └────┘ └──────┘ A B
こうなったとき、辺 $e$ は、
つまり、$A$ 側の頂点に全て $|B|$ を加算し、$B$ 側の頂点に全て $|A|$ を加算すればよい。
これを全ての辺に対して行えば、答えとなる。
加算には、木の累積和を用いる。
適当に頂点1を根としておいて、まず1回目のDFSで各頂点の部分木のサイズ $size[v]$ と深さを求める。
次いで、以下の配列を用意する。最初は全て0。
各辺について、両端の頂点の内、深さが浅い方(親)を $u$、深い方(子)を $v$ とすると、
最後に2回目のDFSで、$Acc$ を根から順に子に伝播させていけばよい。