Let \(N:=N-1\).

We consider BFS-ordered trees as bracket sequences of length \(2N\). Let ( correspond to the operation of going down an edge, and ) correspond to the operation of going up an edge.

Vertex \(N+1\) corresponds to the last point where the height of the bracket sequence is maximized. Vertex \(N\) corresponds to:

• (i) If there are other points at the same height as vertex \(N+1\), the last point among them
• (ii) If there are none, the last point among those at height \(1\) lower than vertex \(N+1\)

We separate the bracket sequence at these two vertices and denote the result as \(X,Y,Z\). For each case, we consider the distance between vertices \(N\) and \(N+1\).

• (i) \(Y\) is a bracket sequence (but with the roles of ( and ) reversed). If we set its height as \(h\), the distance between the two vertices is \(d=2h\).
• (ii) \(Y=\) ) \(+\) bracket sequence \(Y'\) (but with the roles of ( and ) reversed). If we set the height of \(Y'\) as \(h\), the distance between the two vertices is \(d=2h+1\).

Since this is difficult to count directly, for each case, we transform the bracket sequence as follows:

• (i) Create the sequence \(Y+Z+X\) and invert ( and )
• (ii) Create the sequence ) \(+Z+X+Y'\) and invert ( and )

What we obtain is a bracket sequence of length \(2N\), and the inverse operation is possible. Let us describe the inverse operation concretely. Given a bracket sequence \(S\) of length \(2N\), we split \(S\) at the first point (other than the beginning) where the height becomes \(0\), and let \(S=A+B\). If the heights of \(A\) and \(B\) are \(a\) and \(b\), respectively, we can see that \(d=\min(2a,2b+1)\).

Expressing \(A=\)(\(+(\)arbitrary bracket sequence \(A')+\)) and letting the height of \(A'\) be \(a'\), we have \(d=\min(2a'+2,2b+1)\).

Ultimately, for each \(d\), it suffices to solve the following problem:

• Count pairs of bracket sequences \((A,B)\) satisfying the following conditions:
• Total length is \(2N-2\)
• Heights of \(A\) and \(B\) are:
  • (i) Both at most \(d\)
  • (ii) One at most \(d\)
  • (iii) \(A\) at most \(d\) and \(B\) at most \(d+1\)

Case (iii) is simple: we just need to count bracket sequences \(S=\)(\(+A+\))\(+B\) with height at most \(d+1\). This can be computed in \(O(N/(d+2))\) using reflection principle.

Cases (i) and (ii) can be computed almost identically, so we explain case (i).

Consider computing \(f(n,d)\), the number of bracket sequences of length \(2n\) with height at most \(d\).

For \(a \leq b\), define \(c(a,b)\) as follows:

• \(c(a,b)=\) the number of shortest paths from \((0,0)\) to \((a,b)\) that do not pass through the region above the line \(y=x+(b-a)\)

It is well-known that \(c(a,b)=\binom{a+b}{a} - \binom{a+b}{a-1}\).

Using the reflection principle, we can express \(f(n,d)\) as a sum of \(\binom{n}{foo}\), and transforming this gives: \(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))\)

By the way, for arbitrary \(n,i,j\), the following holds: \(\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))\).

Taking a path counted as \(c(n-(i+j),n+1+(i+j))\) and splitting the path at the first moment when \((y-x)\) changes from \(2i \to 2i+1\), we can see that it splits exactly into \(c(k-i,k+i)\) and \(c(n-k-j,n-k+j)\).

Using this to transform \(\sum_{0 \leq k \leq n} f(k,d) \times f(n-k,d)\), we ultimately get a weighted sum of \(O(n/(d+2))\) binomial coefficients.

By doing the above for all \(d\), we can find the answer in \(O(N \log N)\) time overall.

Writer’s solution (C++)