期待値の分解

\(d_{P}(u,v)\) を、木 \(T(P)\) における頂点 \(u,v\) の距離とします。また、\(depth_{P}(u) = d_{P}(1,v)\) とします。さらに、\(LCA_P(u,v)\) を木 \(T(P)\) における頂点 \(u,v\) の最近共通祖先とします。

これらの記法と期待値の線形性を用いて、\(P\) が一様ランダムに選ばれる場合の \(d_P(u,v)\) の期待値 \(\mathbb{E}[d_P(u,v)]\) は以下のように表せます。

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

ただし、\(E_v = \mathbb{E}[depth_P(v)]\) です。 また、\(E_v\) は以下の漸化式で計算できます。

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

累積和を用いることで、\(E_1,\dots,E_N\) は逆元前計算を除いて \(\mathrm{O}(N)\) 時間で計算できます。よって、後は \(\mathbb{E}[depth_P(LCA_P(u,v))]\) を計算できれば \(\mathbb{E}[d_P(u,v)]\) が求まります。

LCA の深さの期待値は \(v\) に依らない(!)

\(u,v\) \((1\leq u < v\leq N)\)の LCA の深さの期待値 \(\mathbb{E}[depth_P(LCA_P(u,v))]\) は、実は \(v\) に依らず一定の値となります。このことを簡単に確認していきます。

木 \(T(P)\) において、\(v\) から \(1\) つずつ親方向に移動することを繰り返したときに初めて現れる番号が \(u\) 以下の頂点を \(w_{P}(u,v)\) とします。このとき、\(P\) が一様ランダムに選ばれることから、全ての \(i\) \((1\leq i\leq u)\) について \(w_{P}(u,v) = i\) となる確率は \(1/u\) です。この確率は \(v\) に依りません。

さらに、\(LCA_P(u,v) = LCA_P(u,w_P(u,v))\) であり、\(w_P(u,v)\) は \(P_u,\dots,P_v\) のみに依存し、\(P_1,\dots, P_{u-1}\) には依存しません。このことから、

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

と計算でき、最右辺が \(v\) に依存しないことがわかります。

以降では、\(L_u = \mathbb{E}[depth_P(LCA_P(u,u+1))]\) とし、\(L_1,\dots,L_{N-1}\) の計算法を考えます。これを用いると、求めたい答えは

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

と書けます。

線形時間 DP

\(P_{u+1}\) の値が \(u\) かそうでないかによって場合分けすることで、\(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} \]

再び累積和を用いることで、\(L_1,\dots,L_{N-1}\) は逆元前計算を除いて \(\mathrm{O}(N)\) 時間で計算できます。