もとの木における、辺 \((u, v)\) （の間に追加される辺）の寄与を考えます。また、頂点 \(u\) の部分木の頂点数を簡単に \(\text{sub}[u]\) と書きます。

頂点の追加は ポリアの壺モデル で表現できます。具体的には 辺 \((u, v)\) で切ったときの ( \(u\) 側 , \(v\) 側 , \(u- v\) 間 ) のどこかに頂点（辺）が追加されるというモデルです。初期状態は \((a_1,a_2,a_3) = (\text{sub}[u]-1, N-\text{sub}[u]-1, 1)\) です。

このポリアの壺モデルにおいて、以下の式が成り立ちます。（簡単な証明は、操作回数に対して数学的帰納法を回すことになるので、略させてください）

\[\displaystyle E\left[\prod x_i^{\overline{m_i}} \right] = \frac{X^{\overline{M}}}{A^{\overline{M}}} \prod a_i^{\overline{m_i}}\]

ただし \(A,M,X\) はそれぞれ \(a_i,m_i,x_i\) の総和、 \(a _i\) は初期のボールの数、\(x_i\) は最終的なボールの数です。

ここで、今回求める期待値は、以下のように全ての項が \(M = 3\) の上昇階乗冪の和で書けることがわかります。

\[\displaystyle x_1x_2x_3 + \frac{1}{2} x_1x_3^{\overline2} + \frac{1}{2} x_2x_3^{\overline2} + \frac{1}{6} x_3^{\overline3}\]

ということで、初期状態の解 \(\displaystyle \sum_{u} \text{sub}[u] \times (N-\text{sub}[u])\) に \(\displaystyle \frac{X^{\overline{M}}}{A^{\overline{M}}} = \frac{(K+N-1)^{\overline{3}}}{(N-1)^{\overline{3}}}\) を掛ければよいです。