グラフの連結成分が含む頂点数のことを連結成分のサイズと表現します。

次のように問題を言い換えます。

\(1\) から \(N\) までの整数からなる順列 \(P=(P_1,P_2,\dots,P_N)\) を一様ランダムに選ぶ。カウンター \(X\) を \(X=0\) で初期化し、 \(i=1,2,\dots,N\) の順に以下を行う。

• 頂点 \(P_i\) を含む連結成分のサイズが \(K+1\) 以上のとき、\(X \leftarrow X+1\) と更新し、頂点 \(P_i\) を端点とする辺をすべて削除する。そうでないとき、なにもしない。

一連の操作終了後の \(X\) の期待値を求めよ。

なにもしない操作を無視すると、次に操作する頂点がサイズが \(K+1\) 以上の連結成分に属する頂点から一様ランダムに選ばれていることに注意してください。

この言いかえの下で計算方法を考えます。グラフの部分木 \(T'\) に対して、一連の操作の最中 \(P_i\) が属する連結成分が \(T'\) であったことがある確率を \(p(T')\) とおくと、期待値の線形性から答えはサイズが \(K+1\) 以上である \(T'\) に対する \(p(T')\) の総和になります（各頂点 \(v\) に対して操作でカウンターへの加算が行われる確率の和などを考えたくなるかもしれませんが、結局 \(v\) が属する連結成分がどのようなものか決めなければならないことを考慮すると、このように考えるのは自然です）。

\(p(T')\) の計算について考えます。\(T'\) に含まれる頂点の数を \(n\) 、元の木グラフにおいて \(T'\) と辺で直接つながっている頂点の数を \(m\) とします。一連の操作で \(v\) が属する連結成分が \(T'\) であったことがあるのは、\(n\) 頂点よりも先に \(m\) 頂点が選ばれるときです（ \(m\) 頂点が選ばれた際辺の削除が起こるかについては、削除前は \(K+1 \leq n\) 頂点と 連結であるため、必ず削除が行われるとわかります）。よって \(p(T')=\frac{n!m!}{(n+m)!}\) と求まります。

以上より問題の答えは、各 \(n,m\) に対し、\(T'\) に含まれる頂点の数が \(n\) 、元の木グラフにおいて \(T'\) と辺で直接つながっている頂点の数が \(m\) であるような部分木 \(T'\) の数が求まれば計算することができます。これは木dpにより計算することができ、いわゆる木の二乗dpと同じ解析を行うと \(O(N^2K^2)\) で求めることができており、十分高速です（定数倍が小さいので \(\Theta(N^3K^2)\) でも通るかもしれません）。