余事象を考えます。

条件を満たさないとは、3頂点がある単純パス上にあるということです。 頂点 \(a, b, c\) がこの順に単純パス上にあるとします。 この時、 \(a, c\) を決め打つと、 \(b\) としてあり得る個数は \({\rm dist}(a, c)-1\) 通りです。 したがって、条件を満たさない組の個数は

\[\sum_{a=1}^{N-1} \sum_{c=a+1}^N ({\rm dist}(a, c)-1) = \left\{ \sum_{a=1}^{N-1} \sum_{c=a+1}^N {\rm dist}(a, c) \right\} - \frac{N(N-1)}{2}\]

です。 これは典型90問 039 - Tree Distance（★5）と同じ問題です。