(より詳しい解説は後日ブログで公開します)

二分木で長さ \(N\) の walk を数える問題だと思うことにします．始点と終点の LCA の深さが \(A\) で，始点と終点の深さはそれぞれ \(A+B, A+C\) です．

walk で訪れる頂点すべての LCA は \(2^{A-a}\) とおけますが，これで場合分けします．

walk を，始点から \(2^{A-a}\) までのパスの \(B+a\) 本の辺を最初に使うステップたちと，終点から \(2^{A-a}\) までのパスの \(C+a\) 本の辺を最後に使うステップたちで区切ります．すると区切られた部分は \(B+C+2a+1\) 個あり，各部分は二分木の根から根までの walk とみなせます．

根から根までの長さ \(i\) の walk は \(2^i C_i\) 個です (\(C_i\) は Catalan 数)．よって，偶奇や不等式を適当に処理した後は，Catalan 数の母関数を \(C(x)\) として \([x^n] C(x)^d\) という形の値を求めることに帰着されます．これはよく知られていて，例えば Lagrange 反転などにより求まり，\(\frac{d}{n} \binom{d-1+2n}{n-1}\) となります．

適切な前計算のもと各 \(a\) を \(O(1)\) 時間で処理できて，全体で \(O(N+A+B+C)\) 時間です．