\(f(p, u, v)\) を以下のように定義します。

• \(T\) をランダムに取ったとき、\(u\) から \(v\) のパス上に、\(p\) と \(p\) の親を結ぶ辺が存在する確率

\(u < v\) が成り立つとき、\(f(p, u, v)\) について、以下が成り立ちます。

• \(2\leq p < u\) ならば、\(f(p, u, v) = (p - 1) \times \frac{p + 2}{p}\times \frac{p + 3}{p + 1} \times \cdots \times \frac{u}{u - 2}\times\frac{2}{u(u - 1)}\)
• \( p = u\) ならば、\(f(p, u, v) = \frac{u - 1}{u}\)
• \(u < p < v\) ならば、\(f(p, u, v) = \frac{1}{p}\)
• \(p = v\) ならば、\(f(p, u, v) = 1\)
• \(v < p\) ならば、\(f(p, u, v) = 0\)

以上の性質と累積和等の適切な前計算を用いると、クエリを定数時間で処理できるので、時間計算量 \(O(N + Q + \log{mod})\) でこの問題を解くことができます。

c++ による実装例

\(f(p, u, v)\) について、上記が成り立つ理由を \(p\) の大きい順に説明します。

\(v < p\)

\(u, v\) の親はそれぞれの番号より小さいことから、\(f(p, u, v) = 0\) が成り立ちます。

\(p = v\)

\(u\) が \(v\) の子孫になることはあり得ないので、\(v\) とその親を結ぶ辺は必ず \(u, v\) のパス上に存在します。

\(u < p < v\)

\(v\) の親を決めるときに、\(p\) の子孫を選んでいれば、この辺は採用されます。これはポリアの壺という有名問題について考えれば、\(f(p, u, v) =\frac{1}{p}\) であることがわかります。

参考 : 高校数学の美しい物語

\(p = u\)

\(v\) の親を決めるときに、\(p\) の子孫を選んでいなければ、この辺は採用されます。上記と同様に \(f(p, u, v) =\frac{u - 1}{u}\) であることがわかります。

\(2\leq p < u\)

\(f(p, u, v)\) は以下の確率と同じです。

• \(u, v\) のうち、ちょうど \(1\) つのみが \(p\) の子孫である確率。

\(T\) を \(u - 1\) 頂点まで決めたとき、\(p\) を根とする部分木のサイズが \(x\) であったとします。

\(u\) のみが \(p\) の子孫である確率は、ポリアの壺と同様の考えで \(\frac{x(u - 1 - x)}{(u - 1)u}\) となります。

同様に、\(v\) のみが \(p\) の子孫である確率は、\(\frac{x(u - 1 - x)}{(u - 1)u}\) となります。

よって、\(f(p, u, v) = E[x(u - 1 - x)]\times \frac{2}{(u - 1)u}\) となります。

\(E[x(u - 1 - x)]\) は以下の問題と同値です。

変数 \(s, t\) が \(s = 1, t = p - 1\) で初期化されています。以下の操作を \(u - 1 - p\) 回行います。

• \(\frac{s}{s + t}\) の確率で \(s\) を \(1\) 増やし、\(\frac{t}{s + t}\) の確率で \(t\) を \(1\) 増やす。

このとき、最終的な \(s\times t\) の期待値を求めてください。

\(1\) 回の操作で \(s\) が \(1\) 増える確率は \(\frac{s}{s + t}\) で、積の増分は \(t\) です。

\(1\) 回の操作で \(t\) が \(1\) 増える確率は \(\frac{t}{s + t}\) で、積の増分は \(s\) です。

よって、\(1\) 回の操作で積は \(\frac{2st}{s + t}\) だけ増えます。これは、積の値によらず、積の値が \(\frac{s + t + 2}{s + t}\) 倍されるということを表しています。

この倍率は \(s + t\) の値にしかよらないことを用いると、\(f(p, u, v)\) は最初に記述した値になります。