#P5410. [2018年湖南省队集训]分岔路口
[2018年湖南省队集训]分岔路口
题目描述
给定一棵树。每次询问给出起点和终点,求采用最优策略从起点到达终点所需的期望步数。
每步可以任选下列一种移动方式:
- 沿当前顶点的一条边移动到另一端。
- 在树的全部顶点中等概率随机选取一个,并移动到该顶点。
输入格式
第一行两个正整数 ,表示顶点数和询问数。
接下来 行,每行两个正整数 ,表示连接顶点 的一条边。
接下来 行,每行两个正整数 ,表示从 移动到 的询问。
输出格式
输出 行,每行一个实数,表示对应询问的最小期望步数。绝对误差不超过 即视为正确。
样例
4 4
1 2
2 3
3 4
1 1
1 2
1 3
1 4
0.00000000
1.00000000
2.00000000
2.33333333
数据范围
- 对于 的数据,,。
- 对于 的数据,,。
- 对于另外 的数据,树是一条链。
- 对于所有数据,,,,且输入保证为合法的树。