公式解説 について、結論の計算式を示します。

「距離が \(D\) である頂点の組 \((i,j)\)であって、\(i,j\) のLCA (Lowest Common Ancestor) が \(v\)であるようなもの」の個数を考え、これを \(f(v)\) とおきます。

\(v\) の深さを \(d\) とします。

(公式解説)

\(v=i\) または \(v=j\) の場合の数え上げ \(f_1(d)\) 、それ以外の場合の数え上げ \(f_2(d)\) は次の式で表されます。

\[ f_1(d)= \begin{cases} 2^{D+1} & \text{if } d+D \leq N-1\\ 0 & \text{otherwise}\\ \end{cases} .\]

\[ f_2(d)= \begin{cases} 0 & \text{if } 2(N-1-d) \lt D \text{ or } D=1\\ 2^{D-1}(D-1) & \text{otherwise if } d+D \leq N-1\\ 2^{D-1}(2N-2d-D-1) & \text{otherwise} \end{cases} . \]

従って、求める数え上げ \(C\) （ \(998244353\) で割った余りを求める前の値）は次のように表されます。

\[C=\sum_{d=0}^{N-1}2^d(f_1(d)+f_2(d)).\]

\(k=0,1,2, \ldots ,2N\) について \(2^k\) の値 \(\pmod{998244353}\)を前計算すると、求める値を計算量 \(O(N)\) で計算できます。

解答例(C++)