題敘

Link
對一棵樹 $T$，節點分節編號為 $1\sim n$，依序操作這件事直到只剩下一個節點：

1. 隨機選定樹當中的其中一條邊，每條邊被選中的機率相同
2. 把這條邊縮起來，假設這條邊連接 $u,\,v$，把 $u$ 跟 $v$ 都拿掉，建一個新的節點連接原本跟 $u$ 或 $v$ 的節點，並且隨機標成 $u$ 或 $v$，標號選擇的機率也是相同的

對每個點輸出，只剩下那個點的機率是多少？輸出在相對或絕對誤差 $10^{-6}$ 以內都會被視為正確。
$ 1 \leq n \leq 50$。

題解

因為這場沒有題解，參考了這篇中國人寫的題解跟那場比賽的 comment 之後，我有了個比較沒那麼數學的講法。

如何下手

因為直覺會發現子樹內除非被縮起來了，不會互相影響，很容易就往 DP 想。
隨便想個 DP 的話，通常會想到類似 $dp_{i,\,j}$ 表示節點 $i$ 的子樹還有 $j$ 條邊之類的東西，
或是 $dp_{i,\,j}$ 表示節點 $i$ 的子樹的根還要跟 $j$ 條邊打架，但做一做就很容易會發現這些東西會跟樹的形狀有關係，沒辦法好好維護。
所以我們想要定一個跟樹的形狀沒有關係的狀態，要怎麼處理？

先把問題重新定好，也就是選定一個邊的排列然後依序縮邊，就可以發現一些根跟他小孩的關係：
考慮根 $r$ 只有一個小孩 $v$，仔細思考 $r$ 會在什麼狀況底下存活，這裡我們可以想成是把這條邊 $(r,\,v)$ 插到 $v$ 子樹中所有邊的排列，看看會發生什麼事。

觀察：
在 $(r,\,v)$ 這條邊加進去的位置之前的邊都不用考慮他們的勝負，只需要在乎這條邊根要打贏，還有之後的邊只要與他相關的邊都需要打贏。

到這裡就有些想法了，一旦這條邊被縮起來而且打贏了，就需要看後面的邊，而這件事剛好會是可以由子樹計算好的東西。
於是 DP 的狀態就可以這樣定義：
$dp_{i,\,j}$ 表示節點 $i$ 的子樹的根在前 $j$ 次縮邊保證存活的話，繼續存活到最後的機率是多少。
這裡的保證存活可以看成，縮點一定會留根。

轉移

轉移的部分可以拆成兩塊來看：加入祖先到小孩的一條邊以及對同一個祖先的合併。

加入祖先到小孩的一條邊

這個 case 在剛剛其實已經有處理過了，這裡我們把他的 $dp$ 式子寫開。
考慮在計算時，我們令 $i$ 的祖先是 $r$，加完 $(r,\,i)$ 這條邊之後的表格是 $dp'_{i,\,j}$，原先的表格是 $dp_{i,\,j}$，
這裡有兩個 case：

1. $(r,\,i)$ 在前 $j$ 條邊裡
   回想狀態的定義，前 $j$ 次縮邊保證存活，所以這邊的機率是 $i$ 子樹內剩下的前 $j-1$ 條都保證存活，存活的機率是 $dp_{i,\,j-1}$。
2. $(r,\,i)$ 不是前 $j$ 條邊，是第 $k$ 條邊
   這時候並沒有保證存活，但只要考慮這條邊打贏，打的人是不是 $i$ 我都無所謂，所以前面任何一次縮邊就算會把 $i$ 打爆，也可以假裝是 $i$（因為他會站在 $i$ 的位置），存活的機率是 $\frac 1 2 dp_{i,\,k-1}$。

因為在每個位置都是均勻的機率，假如 $i$ 子樹是 $T_i$，這些機率要再除上 $|T_i|$（子樹的大小）。

對同一個祖先的合併

因為子樹間的順序不會互相影響，而且我們算的機率是根存活的機率，所以可以直接用類似背包的方式解掉。
關鍵是組合數量相等，也就是，先假設 $r$ 只有兩個小孩 $c_1,\,c_2$：

$$dp_{r,\,j} \binom{|T_r|-1}{j} = \sum_{j_1+j_2=j}dp'_{c_1,\,j_1}\binom{|T_{c_1}|}{j_1}dp'_{c_2,\,j_2}\binom{|T_{c_2}|}{j_2}$$

看上去太數學的話，可以想成在 $r$ 的子樹裡，總共取 $j$ 條邊的方法是 $\binom{|T_r|-1}{j}$，
在在$r$ 這個點以及 $c_1$ 的子樹 $j_1$ 個邊的方法，會是 $\binom{|T_{c_1}|}{j_1}$，
因此「在 $r$ 這個點以及 $c_1$ 的子樹裡，要是前 $j_1$ 個邊都保證存活，$r$ 可以活到最後」的方法數就會是 $dp'_{c_1,\,j_1}\binom{|T_{c_1}|}{j_1}$。
同理「在 $r$ 這個點以及 $c_2$ 的子樹裡，要是前 $j_2$ 個邊都保證存活，$r$ 可以活到最後」的方法數就會是 $dp'_{c_2,\,j_2}\binom{|T_{c_2}|}{j_2}$。
因為 $r$ 存活要在兩個子樹都存活，所以總共的方法數應該加起來要一樣，就得到上面的式子了。

在多個子樹的情況，就直接用推廣的方式，把它當作是一種背包問題，改寫成 $$dp_{r,\,j} \leftarrow \frac{{\displaystyle\sum_{j_1+j_2=j}}dp_{r,\,j_1}\binom{|T_{r}|-1}{j_1}dp'_{c,\,j_2}\binom{|T_c|}{j_2}}{\binom{|T_r|-1}{j}}$$ 這裡的陣列需要開新的算好再賦值，子樹大小 $|T_r| = 1$，每次轉移完更新為 $|T_r| \leftarrow |T_r| + |T_c|$，
並且設定 DP 初始值 $dp_{r,\,0} = 1$ 就好了。

複雜度分析

1. 加入祖先到小孩的一條邊
   顯然是 $\mathcal O(n^3)$。
2. 對同一個祖先的合併 如果 DP 表格的大小有好好照著動態轉移的順序變動，會是 $\mathcal O(n^3)$，因為可以用均攤的看成把子樹合併的時候，相當於把兩邊子樹都配對起來，然後合併成一個比較大的點集，所以每對點對剛好算過一次，複雜度 $\mathcal O(n^2) \times \mathcal O(n)$ 的狀態量。

對每個根都跑一次，費時 $\mathcal O(n^4)$。

Code

AC Code

第一次看到這種定狀態的方法 OAO