AC代碼

https://codeforces.com/contest/1770/submission/188152394

題意：

Imi有一個具有n個頂點的無向樹，其中邊的編號從1到n?1。第i條邊連接頂點ui和vi。

樹上還有k只蝴蝶。最初，第i個蝴蝶位于頂點ai上。?

Koxia玩的游戲如下：

1. 對于i=1,2，…，n?1，Koxia將第i條邊的方向設置為ui→vi或vi→ui的概率相等。

2. 對于i=1,2，…，n?1，如果一只蝴蝶在第i條邊的初始頂點上，而末端頂點上沒有蝴蝶，

那么這只蝴蝶會飛到末端頂點。注意，操作順序為1,2，…，n?1，而不是同時進行。

3. Koxia從所有可能的k(k?1)/2種方式中以相等的概率從k只蝴蝶中選擇兩只蝴蝶來選擇兩只蝴蝶，

然后她將兩個選擇的頂點之間的距離作為她的分數(shù)。

現(xiàn)在，Koxia希望你找到她的分數(shù)的期望值，模998244353。

題解：

?組合數(shù)學 + 圖論 + 概率論