頂点対 \((i, j)\ (i\lt j)\) であって、距離がちょうど \(d\) であるようなものの個数を \(\mathsf{freq} (d)\) とします。

このとき、補集合を考えることで答えは次のように表せます。

\[\binom{n}{3} - \sum _ {d = 2} ^ {n - 1} (d - 1) \times \mathsf{freq} (d).\]

\(\mathsf{freq} (2), \ldots, \mathsf{freq}(n - 1)\) の列挙は重心分解と FFT を用いた畳み込みで \(O(n (\log n) ^ 2)\) 時間で計算できることが知られています。(参考: https://judge.yosupo.jp/problem/frequency_table_of_tree_distance)

従って、本問題を \(O(n (\log n) ^ 2)\) 時間で解くことができました。