First, \(\text{dist}(i,j)\) equals \(1\) plus the number of vertices on the \(i\)–\(j\) path (excluding \(i\) and \(j\)). Also, the sum of “the number of vertices on the \(i\)–\(j\) path (excluding \(i\) and \(j\))” over all vertex pairs \(\lbrace i,j\rbrace\) equals “the number of sets \(\lbrace a,b,c\rbrace\) such that a path passing through all of \(a,b,c\) exists,” which can be seen by fixing an interior vertex and counting.

By considering the complementary event, “the number of sets \(\lbrace a,b,c\rbrace\) such that a path passing through all of \(a,b,c\) exists” equals \(\displaystyle \frac{N'(N'-1)(N'-2)}6\) (where \(N'\) is the number of vertices) minus “the number of sets \(\lbrace a,b,c\rbrace\) such that a path passing through all of \(a,b,c\) does not exist.”

The non-existence of a path passing through all of \(a,b,c\) is equivalent to the existence of a vertex \(v\) such that when \(v\) is removed, vertices \(a,b,c\) belong to different connected components. Furthermore, in such a case, there is exactly one such \(v\) for which the vertex sets on the \(v\)–\(a\), \(v\)–\(b\), \(v\)–\(c\) paths are pairwise disjoint except for \(v\). Fixing such a \(v\), “the number of sets \(\lbrace a,b,c\rbrace\) such that a path passing through all of \(a,b,c\) does not exist” can be expressed as the sum over \(v=1,2,\ldots,N\) of “\(\displaystyle \sum_{1\le i < j < k \le |C^v|} C_i^vC_j^vC_k^v\), where \(C_1^v,C_2^v,\ldots,C_{|C^v|}^v\) are the sizes of the connected components when vertex \(v\) is removed.” We call this value the score of \(v\).

Here, consider the following problem.

You are given a sequence of positive integers \(A=(A_1,A_2,\ldots,A_n)\) of length \(n\) and an integer \(k\).

Perform the following operation on \(A\) exactly \(k\) times.

• Choose an integer \(1\le i\le n\) at random, where \(i\) is chosen with probability \(\displaystyle \frac{A_i}{\sum A}\). Then, increase \(A_i\) by \(1\).

Find the expected value of \(\displaystyle \sum_{1\le i < j < k \le n} A_iA_jA_k\) after \(k\) operations.

First, fix a tuple of integers \((i,j,k)\) and consider by how much \(A_iA_jA_k\) increases in one operation.

For \(A_iA_jA_k\) to change, one of \(i,j,k\) must be chosen. Computing the increment for each case, the expected value of \(A_iA_jA_k\) after one operation is \(\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\). Since \(\displaystyle 1+\frac3{\sum A}\) does not depend on \(i,j,k\), the expected value of \(\displaystyle \sum_{1\le i < j < k \le n} A_iA_jA_k\) is multiplied by \(\displaystyle 1+\frac3{\sum A}\) in one operation. Repeating this \(k\) times, the desired expected value is \(\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\), where \(\displaystyle T=\sum A\).

Based on the above, let us solve the original problem.

Since the degree of the new vertex added by the operations is always \(2\), the score of \(v\) is \(0\) for \(v>N\).

Let \(f(k)\) be the expected value when \(K=k\). The desired answer is \(f(K)\).

Setting \(\displaystyle X_k=\frac{(N+k)(N+k-1)(N+k+1)}{N(N-1)(N+1)}\), the expected score of \(v=1,2,\ldots,N\) after \(k\) operations is \(X_k\) times the original score. Thus, letting \(S\) be the sum of the original scores,

\[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\]

holds, and by comparing this expression at \(k=0\) and \(k=K\), we obtain \(\displaystyle f(K)=X_Kf(0)\). Since \(f(0)\) is \(\displaystyle \sum_{1\le i < j \le N} \text{dist}(i,j)\) for the given tree, it can be computed easily via tree DP or similar methods. \(X_K\) can also be computed easily, so \(f(K)\) can be obtained from these.

By implementing the above appropriately, this problem can be solved. The time complexity is \(O(N)\).

Proposed by: nok0