#P17911. Fallleaves01 and Golf

Fallleaves01 and Golf

题目描述

有 kk 棵树,第 ii 棵树有 nin_i 个顶点,编号为 11 至 nin_i。每棵树的顶点 11 都是终点,树上各有一个球,初始位于顶点 sis_i。

每次操作,你根据当前所有球的位置选择一个球。这个球会等概率移动到它当前顶点的某个相邻顶点,其他球不动。每次操作的代价为 11。

只要任意一个球到达其所在树的顶点 11,整个过程立即结束。你可以在后续操作中改变选择,并利用之前观察到的移动结果。

求采用最优策略时,结束过程所需操作次数的最小期望值。

输入格式

每个文件只有一组数据。

第一行是整数 kk。随后依次描述 kk 棵树。对于每棵树:

  • 第一行是 ni,sin_i,s_i。
  • 接下来 ni−1n_i-1 行,每行两个整数 u,vu,v,表示一条无向边。

输出格式

输出一个实数,表示最小期望操作次数。

设输出为 aa,正确答案为 bb,满足

∣a−b∣max⁡(1,∣b∣)≤10−6\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}

即被接受。

数据范围

1≤k≤3001\le k\le300,2≤si≤ni≤3002\le s_i\le n_i\le300,边端点在 [1,ni][1,n_i] 内。每段边列表保证构成一棵树。

样例

2
4 2
1 2
2 3
3 4
4 3
1 2
2 3
3 4
4.666666666666666