首页 > 试题广场 >

托米的游戏

[编程题]托米的游戏
题目背景编不下去了

托米有一棵有根树 T, 树根为1，每轮他会在剩下的子树中等概率一个点 u, 砍掉 u 的子树 (包含 u)，如果树上的点都被砍光了，游戏结束。

求出这个游戏进行的期望轮数，可以证明这个数一定是有理数，设他为 , 你需要告诉他一个整数 x 满足

输入描述:
第一行输入一个数 n， 表示 T 的点数，下面 n-1 行给出了 T 的每条边


输出描述:
一行一个整数表示答案
示例1

输入

3
1 2
1 3

输出

2

备注:
n ≤ 105
算法知识视频讲解
开通博客
头像 威风镰鼬
发表于 2021-11-25 01:23:02
思路 对于每个节点来说，对答案的期望贡献都是其深度的倒数。因此，我们只要将每个点贡献累加就能得到最终期望。 用快速幂求每个贡献(1dep[i]\frac{1}{dep[i]}dep[i]1​)的逆元，再相加就是最终答案。 代码 #include<bits/stdc++.h> #defin 展开全文
去ta的博客 赞 (2) 回复(1) 收起

问题信息

深度优先搜索(DFS) 数论
上传者：牛客301599号
难度：
0条回答 387浏览

热门推荐

通过挑战的用户

查看代码

相关试题

托米的游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号