余事象を考えます.

条件を満たさないとは, 3頂点がある単純パス上にあるということです.頂点 \(a,b,c\) がこの順に単純パス上にあるとします.

「連続する3点は真ん中の1点を固定する」という典型に基づき, \(b\) を固定します.
木から \(b\) を除いて出来る各連結成分のサイズを \(m_1,\dots,m_k\) とすると, \(\sum_{i<j} m_im_j\) が固定した \(b\) に対して求めたいものです.
\(2\sum_{i<j} m_im_j = (\sum m_i)^2 - \sum m_i^2\) の式変形を用いることでこれは \(O(k)\) で求めることができます.

木を(頂点0を根とした）根付き木として各頂点 \(v\) に対し \(v\) を根とする部分木のサイズを前計算 \(O(n)\) で求めておくことで, 各 \(b\) に対して \(m_1,\dots,m_k\) は \(O(k)\) で求めることが出来るので, 全体として \(O(n)\) でこの問題を解くことができました.

実装例（C++）