Decomposing the Expected Value

Let \(d_{P}(u,v)\) be the distance between vertices \(u\) and \(v\) in the tree \(T(P)\), and let \(depth_{P}(u) = d_P(1,u)\). Moreover, let \(LCA_P(u,v)\) be the lowest common ancestor of \(u\) and \(v\) in \(T(P)\).

Using this notation and linearity of expectation, the expected distance \(\mathbb{E}[d_{P}(u,v)]\) for \(P\) chosen uniformly at random can be written as:

\[ \mathbb{E}[d_P(u,v)] = E_u + E_v - 2\cdot \mathbb{E}[depth_P(LCA_P(u,v))], \]

where \(E_v = \mathbb{E}[depth_P(v)]\). In addition, \(E_v\) satisfies the recursion:

\[ E_v = \begin{cases} 0 & (v = 1)\\ A_v + \frac{1}{v-1}\sum_{i=1}^{v-1}{E_i} & (2\leq v\leq N) \end{cases} \]

Using prefix sums, you can compute \(E_1,\dots,E_N\) in \(\mathrm{O}(N)\) time, apart from precomputing inverses. Therefore, what remains is to compute \(\mathbb{E}[depth_P(LCA_P(u,v))]\).

The Expected Depth of the LCA Does Not Depend on \(v\) (!)

Consider \(LCA_P(u,v)\) for \(1 \leq u < v \leq N\). Its expected depth \(\mathbb{E}[depth_P(LCA_P(u,v))]\) actually does not depend on \(v\). Let us verify this.

In the tree \(T(P)\), let \(w_P(u,v)\) be the first vertex with index at most \(u\) that appears when moving parentward from \(v\) step by step. Since \(P\) is chosen uniformly at random, the probability that \(w_P(u,v) = i\) is \(1/u\) for each \(1 \leq i \leq u\). This probability does not depend on \(v\).

Moreover, \(LCA_P(u,v) = LCA_P(u, w_P(u,v))\), and \(w_P(u,v)\) depends only on \(P_u, \dots, P_v\), not on \(P_1,\dots,P_{u-1}\). Hence:

\[ \begin{aligned} \mathbb{E}[depth_P(LCA_P(u,v))] &= \mathbb{E}[depth_P(LCA_P(u,w_P(u,v)))]\\ &= \frac{1}{u}\sum_{i=1}^{u} \mathbb{E}[depth_P(LCA_P(u,i))], \end{aligned} \]

and the rightmost hand side does not depend on \(v\).

Define \(L_u = \mathbb{E}[depth_P(LCA_P(u,u+1))]\). Let us consider how to compute \(L_1,\dots,L_{N-1}\). Using these, the desired answer is:

\[ \mathbb{E}[d_P(u,v)] =E_u + E_v- 2\cdot L_u. \]

Linear-Time DP

By separating the case \(P_{u+1} = u\) from \(P_{u+1} \neq u\), one obtains the following recursion for \(L_u\):

\[ \begin{aligned} L_u &= \mathbb{E}[depth_P(LCA_P(u,u+1))]\\ &= \frac{1}{u}\left(\mathbb{E}[depth_P(u)] + \sum_{i=1}^{u-1}\mathbb{E}[depth_P(LCA_P(u,i))]\right)\\ &= \frac{1}{u}\left(E_u + \sum_{i=1}^{u-1} L_i\right). \end{aligned} \]

By using prefix sums again, you can compute \(L_1,\dots,L_{N-1}\) in \(\mathrm{O}(N)\) time, apart from inverse precomputation.