\(\mathrm{O}(N^2)\) 時間解法

\(dp(u,v)\) を \(P\) が一様ランダムに選ばれるときの、木 \(T(P)\) における頂点 \(u,v\) の距離の期待値とします。\(u = v\) のときは \(dp(u,v) = 0\) です。\(u < v\) のときは \(v\) の親 \(w\) で場合分けすることによって、以下の漸化式が成り立ちます。

\[ dp(u,v)= \begin{cases} 0 & (u = v)\\ dp(v,u) & (u\gt v)\\ A_v + \frac{1}{v-1}\sum_{w=1}^{v-1}dp(u,w) & (u\lt v) \end{cases} \]

累積和を用いることで、全ての \(u,v\) に対する \(dp(u,v)\) を \(\mathrm{O}(N^2)\) 時間で計算できます。

期待値の分解

以降では、\(1\) つ目の公式解説の記法を利用します。

期待値の線形性より、\(dp(u,v)\) は以下のように表せます。

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

また、\(E_1,\dots,E_N\) は DP によって線形時間で計算できます。ここで、\(dp'(u,v) = \mathbb{E}[depth_P(LCA_P(u,v))]\) とすると、\(dp\) の漸化式と同様のものが \(dp'\) に対しても成り立ちます。

\[ dp'(u,v)= \begin{cases} E_v & (u = v)\\ dp'(v,u) & (u\gt v)\\ \frac{1}{v-1}\sum_{w=1}^{v-1}dp'(u,w) & (u\lt v) \end{cases} \]

\(dp(u,v) = E_u + E_v - 2\cdot dp'(u,v)\) なので、\(dp'(u,v)\) が計算できれば良いです。

\(dp'\) は所謂「もらう DP」の形で定式化されていますが、これを「配る DP」の形で再定式化していきます。

配る DP の遷移

\(dp'\) の定義域を \(1\leq u\leq v\leq N\) に限定すると、漸化式は以下のようになります。

\[ dp'(u,v)= \begin{cases} E_v & (u = v)\\ \frac{1}{v-1}\lbrace\sum_{w=1}^{u-1}dp'(w,u) + \sum_{w=u}^{v-1}dp'(u,w)\rbrace & (u\lt w) \end{cases} \]

これを配る DP の視点で見ると、以下のことがわかります。

• \((v,v)\) に \(E_v\) の湧き出し
• \(u\lt v\) のとき、各 \(w\) \((v+1\leq w\leq N)\) について \((u,v)\) から \((v,w)\) への \(1/(w-1)\) 倍の寄与
• \(u\leq v\) のとき、各 \(w\) \((v+1\leq w\leq N)\) について \((u,v)\) から \((u,w)\) への \(1/(w-1)\) 倍の寄与

以降では、\(2\) つ目の寄与、\(3\) つ目の寄与をそれぞれ寄与 A、寄与 B と呼びます。

\((w,w)\) から \((u,v)\) への寄与

\((w,w)\) から \((u,v)\) への寄与のを考えます。\(w\gt u\) の場合は寄与は \(0\) です。

\(w < u\) の場合

\((x_0,y_0) = (w,w)\) から \((x_1,y_1),\dots,(x_{K-1},y_{K-1})\) を経由して \((x_K, y_K) = (u,v)\) に遷移する寄与を考えます。ここで、寄与が非零になるのは \(y_0\lt y_1\lt\cdots\lt y_K\) かつ、ある \(L\) について \(y_L = u\) となるものに限ります。また、その場合の寄与は

\[ \prod_{k=1}^{K}\frac{1}{y_k-1}\cdot E_w = \prod_{k=1}^{L-1}\frac{1}{y_k-1}\cdot\prod_{k=L+1}^{K-1}\frac{1}{y_k-1}\cdot\frac{E_w}{(u-1)(v-1)} \]

となります。寄与は \(x\) には依存せず \(y\) のみに依存するので、\(y_0,\dots,y_K\) を固定したときの \(x_0,\dots,x_K\) としてあり得るものの個数を考えます。\((x_i,y_i)\) から \((x_{i+1},y_{i+1})\) への寄与の種類について、以下のことがわかります。

• \((x_0,y_0)\) から \((x_1,y_1)\) への寄与は、寄与 B のみ
• \((x_i,y_i)\) から \((x_{i+1},y_{i+1})\) \((1\leq i\leq L-1)\) への寄与は、寄与 A と寄与 B の両方があり得る
• \((x_L,y_L)\) から \((x_{L+1},y_{L+1})\) への寄与は、寄与 A のみ
• \((x_i,y_i)\) から \((x_{i+1},y_{i+1})\) \((L+1\leq i\leq K-1)\) への寄与は、寄与 B のみ

以上より、\(y_0,\dots,y_K\) を固定したときの \(x_0,\dots,x_K\) としてあり得るものは \(2^{L-1}\) 個となります。従って、全ての \(y\) についての寄与

\[ \prod_{k=1}^{K}\frac{1}{y_k-1}\cdot 2^{L-1}\cdot E_w = \prod_{k=1}^{L-1}\frac{2}{y_k-1}\cdot\prod_{k=L+1}^{K-1}\frac{1}{y_k-1}\cdot\frac{E_w}{(u-1)(v-1)} \]

の総和を取ると

\[ \prod_{k=w+1}^{u-1}\left(1 + \frac{2}{k-1}\right)\cdot\prod_{k=u+1}^{v-1}\left(1+\frac{1}{k-1}\right)\cdot\frac{E_w}{(u-1)(v-1)} \]

となります。これが \((w,w)\) から \((u,v)\) への寄与です。

\(w = u\) の場合

前述と同様の計算をすると、\((w,w)\) から \((u,v)\) への寄与は以下のようになります。

\[ \prod_{k=u+1}^{v-1}\left(1+\frac{1}{k-1}\right)\cdot\frac{E_u}{v-1} \]

結論

結論として、\(dp'(u,v)\) は以下のようになります。

\[ \begin{aligned} dp'(u,v) &= \left[ \sum_{w=1}^{u-1}\left\lbrace \prod_{k=w+1}^{u-1}\left(1 + \frac{2}{k-1}\right)\cdot\frac{E_w}{u-1} \right\rbrace +E_u \right] \cdot\prod_{k=u+1}^{v-1}\left(1+\frac{1}{k-1}\right)\cdot\frac{1}{v-1} \\ &= \left[ \sum_{w=1}^{u-1}\left\lbrace \prod_{k=w+1}^{u-1}\left(1 + \frac{2}{k-1}\right)\cdot\frac{E_w}{u-1} \right\rbrace +E_u \right]\cdot \frac{1}{u} \end{aligned} \]

適切な前計算によって、クエリあたり \(\mathrm{O}(1)\) や \(\mathrm{O}(\log\mathrm{mod})\) 時間で解くことができます。全体の計算量は \(\mathrm{O}(N+Q)\) や \(\mathrm{O}((N+Q)\log\mathrm{mod})\) になります。

また、上の \(dp'(u,v)\) の結論式を見ると、この値が実は \(v\) に依存していないこともわかります。