#P17911. Fallleaves01 and Golf
Fallleaves01 and Golf
题目描述
有 棵树,第 棵树有 个顶点,编号为 至 。每棵树的顶点 都是终点,树上各有一个球,初始位于顶点 。
每次操作,你根据当前所有球的位置选择一个球。这个球会等概率移动到它当前顶点的某个相邻顶点,其他球不动。每次操作的代价为 。
只要任意一个球到达其所在树的顶点 ,整个过程立即结束。你可以在后续操作中改变选择,并利用之前观察到的移动结果。
求采用最优策略时,结束过程所需操作次数的最小期望值。
输入格式
每个文件只有一组数据。
第一行是整数 。随后依次描述 棵树。对于每棵树:
- 第一行是 。
- 接下来 行,每行两个整数 ,表示一条无向边。
输出格式
输出一个实数,表示最小期望操作次数。
设输出为 ,正确答案为 ,满足
即被接受。
数据范围
,,边端点在 内。每段边列表保证构成一棵树。
样例
2
4 2
1 2
2 3
3 4
4 3
1 2
2 3
3 4
4.666666666666666