Expected distance between tree nodes I have been given a tree with n nodes and n-1 edges with it's weight.
There are two people A and B.
I have been given a list of nodes of size k.

A will pick a random node x from this list and B will independently pick a random node y from this list.

I have to find expected distance between these two nodes.

My way of solving it was to find the distance between all the (k*(k-1)/2)nodes of the list and dividing it by number of nodes in the list.

for ex:
n=6,k=6 list=[1,2,3,4,5,6]

                    Node--------&gt; 1
                                   \(1)&lt;-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6


My answer was coming out to be 87/6 but the actual answer was 29/6.Please help me find whatever i am doing wrong here.
Let $d(i,j)$ denote the distance between $i$ and $j$. Calculation shows that
$$
\sum_{i&lt;j} d(i,j) = 87.
$$
Hence the average distance is
$$
\frac{1}{6^2} \sum_{i,j=1}^6 d(i,j) = \frac{1}{36} \left(\sum_{i&lt;j} d(i,j) + \sum_{i&gt;j} d(i,j) + \sum_{i=j} d(i,j)\right) = \frac{2\cdot 87}{36} = \frac{29}{6}.
$$

A simple way to do the calculation is as follows. Suppose that there are $n$ nodes, and that edge $e$ of weight $w_e$ cuts the tree into parts of size $k_e,n-k_e$. Then the average distance is
$$
\frac{2}{n^2} \sum_e w_e k_e (n-k_e).
$$
For example, in our case we get
$$
\frac{2}{36} (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) = \frac{29}{6}.
$$