題目：
https://ac.nowcoder.com/acm/problem/16765
托米有一棵有根樹$T$, 樹根為$1$，每輪他會在剩下的子樹中等概率一個點 $u$, 砍掉$u$的子樹 (包含$u$)，如果樹上的點都被砍光了，游戲結(jié)束.求出這個游戲進行的期望輪數(shù)，可以證明這個數(shù)一定是有理數(shù)，設(shè)他為 $\frac{a}{b}$ , 你需要告訴他一個整數(shù)$x$滿足
$xb\equiv a(mod998244353)n\le 10^5$

思路：
按照套路，根據(jù)期望的線性性，和的期望等于期望的和，$E(x)={\sum }_{i=1}^{n}E(x_i)$，期望步數(shù)可以等價于對每個點的期望貢獻單獨算后求和。
考慮一個點被刪除時只有兩種情況(默認根的深度為1)：

• 選中自己被刪除，此時貢獻為1，概率為$\frac{1}{de{p}_i}$
• 選中該點的祖先，此時貢獻為0，貢獻應該被算在祖先處，概率為$\frac{de{p}_i?1}{de{p}_i}$
  PS：刪除其他點并不會導致該點被刪除，不會對它的概率產(chǎn)生影響。
  所以$E(x)={\sum }_{i=1}^n\frac{1}{de{p}_i}$

總結(jié)

以上是生活随笔為你收集整理的托米的游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。