余事象で考えます。

条件を満たさないとは、3頂点がある単純パス上にあるということです。 適当な根付き木を考えます。 根付き木上の頂点 \(v\) を通るパスを数え上げます。 頂点 \(v\) を通るパスは以下の 2通りが考えられます。

• 頂点 \(v\) の部分木に含まれない頂点から、頂点 \(v\) を通って、頂点 \(v\) の子孫に至る
• 頂点 \(v\) に直接繋がる頂点を \(c_i, c_j\) とすると、頂点 \(c_i\) の部分木から頂点 \(v\) を通って、頂点 \(c_j\) の部分木に至る

よって、上記の 2通りの単純パスの通り数を \( \footnotesize \begin{pmatrix} n \\ 3 \end{pmatrix} \) から引けば答えを計算することができます。

c++ 解答例