首页 > 试题广场 >

托米的游戏

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

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

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

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


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

输入

3
1 2
1 3

输出

2

备注:
n ≤ 105
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

托米的游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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