\(N:=N-1\) とします．

BFS-ordered Tree を，長さ \(2N\) の括弧列で考えます． ( が辺を下る操作，) が辺を上る操作に対応するものとします．

頂点 \(N+1\) に対応するのは，括弧列の高さが最大になる最後の点です． 頂点 \(N\) に対応するのは

• (i) 頂点 \(N+1\) と同じ高さの点がほかにがあるならば，その中で最後の点

• (ii) ない場合は，頂点 \(N+1\) より \(1\) 低い高さのなかで最後の点

となります． \(2\) つの頂点で括弧列を分離し，その結果を \(X,Y,Z\) とおきます． 各ケースについて，頂点 \(N\) と \(N+1\) の距離を考えます．

• (i) \(Y\) が括弧列(ただし () の役割が逆)になるが，その高さを \(h\) と置くと，\(2\) 頂点の距離は \(d=2h\) となる．

• (ii) \(Y=\) ) \(+\) 括弧列 \(Y'\) (ただし () の役割が逆) になるが，\(Y'\) の高さを \(h\) と置くと，\(2\) 頂点の距離は \(d=2h+1\) となる．

このままだと数えづらいので，各ケースについて，括弧列を次のように変形します．

• (i) \(Y+Z+X\) という列を作り，(,) を反転する
• (ii) ) \(+Z+X+Y'\) という列を作り，(,) を反転する

こうして得られるのは長さ \(2N\) の括弧列で，また逆操作が可能になっています． 逆操作を具体的に表します． 長さ \(2N\) の括弧列 \(S\) が与えられたとき，先頭以外で初めて高さが \(0\) になる点で \(S\) を分割し，\(S=A+B\) とします． \(A,B\) の高さをそれぞれ \(a,b\) とすると，\(d=\min(2a,2b+1)\) であることがわかります．

\(A=\)(\(+(\)任意の括弧列\(A')+\))と表し，\(A'\) の高さを \(a'\) とすると，\(d=\min(2a'+2,2b+1)\) です．

結局各 \(d\) に対して，次の問題が解ければ良いです．

• 括弧列の組 \((A,B)\) であって，以下の条件を満たすものを数える．
• 長さの合計が \(2N-2\)
• \(A,B\) の高さが
  • (i) 両方 \(d\) 以下
  • (ii) 片方 \(d\) 以下
  • (iii) \(A\) が \(d\) 以下で \(B\) が \(d+1\) 以下

(iii) のケースは簡単で，括弧列 \(S=\)(\(+A+\))\(+B\) であって高さが \(d+1\) 以下になるものを数えればよいです． これは鏡像反転を使うと \(O(N/(d+2))\) で計算できます．

(i),(ii) のケースはほとんど同じように計算できるため，(i) について説明します．

高さが \(d\) 以下の長さ \(2n\) の括弧列の個数 \(f(n,d)\) の計算を考えます．

\(a \leq b\) に対して \(c(a,b)\) を次のように定義します．

• \(c(a,b)=\) \((0,0)\) から \((a,b)\) に至る最短パスであって，直線 \(y=x+(b-a)\) より上の領域を通らないようなものの数

有名な事実として，\(c(a,b)=\binom{a+b}{a} - \binom{a+b}{a-1}\) です．

鏡像反転を使って \(f(n,d)\) を \(\binom{n}{hoge}\) の和で表すことができますが，これを変形すると \(f(n,d)=(\sum_{i=0,(d+2),(d+2)\times 2,\cdots} c(n-i,n+i)) -( \sum_{i=(d+2)-1,(d+2)\times 2-1,\cdots} c(n-i,n+i))\) となります．

ところで，任意の \(n,i,j\) に対して，\(\sum_{0 \leq k \leq n} c(k-i,k+i) \times c(n-k-j,n-k+j) = c(n-(i+j),n+1+(i+j))\) が成立します．

\(c(n-(i+j),n+1+(i+j))\) として数えられるパスをとり，\((y-x)\) が \(2i \to 2i+1\) と変化する最初のタイミングでパスを分割すると，ちょうど \(c(k-i,k+i)\) と \(c(n-k-j,n-k+j)\) に分かれていることがわかります．

これを使って \(\sum_{0 \leq k \leq n} f(k,d) \times f(n-k,d)\) を式変形すると，最終的に \(O(n/(d+2))\) 個の二項係数の重み付き和になります．

以上をすべての \(d\) に対して行うことで，全体 \(O(N \log N)\) で答えが求まります．

writer解(C++)