まず、\(\text{dist}(i,j)\) は「\(i- j\) パスに含まれる頂点の数(\(i,j\) を除く)」に \(1\) を足した値となります。また、全ての頂点対 \(\lbrace i,j\rbrace\) に対する「\(i- j\) パスに含まれる頂点の数(\(i,j\) を除く)」の総和は、パス内の頂点を固定して数え上げることで「\(a,b,c\) を全て通るパスが存在するような \(\lbrace a,b,c\rbrace\) の個数」と一致することも分かります。

余事象を考えることで、「\(a,b,c\) を全て通るパスが存在するような \(\lbrace a,b,c\rbrace\) の個数」は頂点数を \(N'\) として \(\displaystyle \frac{N'(N'-1)(N'-2)}6\)から「\(a,b,c\) を全て通るパスが存在しないような \(\lbrace a,b,c\rbrace\) の個数」を引いた数と一致します。

\(a,b,c\) を全て通るパスが存在しないことはある頂点 \(v\) が存在し頂点 \(v\) を削除した時に頂点 \(a,b,c\) が異なる連結成分に属していることと同値になります。さらに、そのような場合 \(v-a,v-b,v-c\) パスに属する頂点集合が頂点 \(v\) を除いて互いに素となるような \(v\) がただ一つ存在します。その \(v\) を固定すると「\(a,b,c\) を全て通るパスが存在しないような \(\lbrace a,b,c\rbrace\) の個数」は \(v=1,2,\ldots,N\) に対する「頂点 \(\displaystyle v\) を削除した時の各連結成分のサイズを \(C_1^v,C_2^v,\ldots,C_{|C^v|}^v\) として \(\displaystyle \sum_{1\le i < j < k \le |C^v|} C_i^vC_j^vC_k^v\) 」の総和と表されることが分かります。この値を \(v\) のスコアと呼びます。

ここで、以下のような問題を考えます。

長さ \(n\) の正整数列 \(A=(A_1,A_2,\ldots,A_n)\) と整数 \(k\) が与えられる。

\(A\) に対して以下の操作を \(k\) 回行う。

• 整数 \(1\le i\le n\) をランダムに選ぶ。ここで、\(i\) が選ばれる確率は \(\displaystyle \frac{A_i}{\sum A}\) とする。その後、\(A_i\) の値を \(1\) 増やす。

\(k\) 回の操作後の \(\displaystyle \sum_{1\le i < j < k \le n} A_iA_jA_k\) の期待値を求めよ。

まず整数組 \((i,j,k)\) を固定し、\(1\) 回の操作で \(A_iA_jA_k\) の値がどれだけ増えるかを考えます。

\(A_iA_jA_k\) の値が変わるには \(i,j,k\) のいずれかが選ばれる必要があります。それぞれについて増分を計算すると、\(1\) 回の操作後の \(A_iA_jA_k\) の期待値は \(\displaystyle A_iA_jA_k+A_jA_k\times \frac{A_i}{\sum A}+A_iA_k\times \frac{A_j}{\sum A}+A_iA_j\times \frac{A_k}{\sum A}=\left(1+\frac3{\sum A}\right)A_iA_jA_k\) となります。\(\displaystyle 1+\frac3{\sum A}\) の値は \(i,j,k\) に依存しないので、\(1\) 回の操作で \(\displaystyle \sum_{1\le i < j < k \le n} A_iA_jA_k\) の期待値は \(\displaystyle 1+\frac3{\sum A}\) 倍されることが分かります。これを \(k\) 回繰り返すことで、求める期待値は \(\displaystyle T=\sum A\) として \(\displaystyle \frac{(T+k)(T+k+1)(T+k+2)}{T(T+1)(T+2)}\sum_{1\le i < j < k \le n} A_iA_jA_k\) となります。

以上を元にして元の問題を解くことを考えます。

各操作によって増える頂点の次数は必ず \(2\) であるため、\(v>N\) に対する \(v\) のスコアは \(0\) になります。

\(f(k)\) を \(K=k\) の場合の期待値とします。求める答えは \(f(K)\) です。

\(\displaystyle X_k=\frac{(N+k)(N+k-1)(N+k+1)}{N(N-1)(N+1)}\) として、\(v=1,2,\ldots,N\) に対し \(k\) 回後のスコアの期待値は元のスコアの \(X_k\) 倍となります。したがって、元のスコアの総和を \(S\) とすると、

\[f(k)=\displaystyle \frac{(N+k)(N+k-1)}2+\frac{(N+k)(N+k-1)(N+k-2)}6-SX_k=\left(\frac{N(N-1)(N+1)}6-S\right)X_k\]

が成り立ち、この式の \(k=0,K\) を比較することで \(\displaystyle f(K)=X_Kf(0)\) が得られます。 \(f(0)\) は与えられた木に対する \(\displaystyle \sum_{1\le i < j \le N} \text{dist}(i,j)\) なので、木 DP などで簡単に計算できます。\(X_K\) も簡単に計算できるので、これらを元に \(f(K)\) の値も求めることができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N)\) です。

原案：nok0