#P5410. [2018年湖南省队集训]分岔路口

    ID: 4422 传统题 8000ms 512MiB 尝试: 111 已通过: 32 难度: 9 上传者: 标签>CF2600提高+/省选-期望方程二分答案点分治点分治容斥去重一维前缀和LCA树上倍增

[2018年湖南省队集训]分岔路口

题目描述

给定一棵树。每次询问给出起点和终点,求采用最优策略从起点到达终点所需的期望步数。

每步可以任选下列一种移动方式:

  • 沿当前顶点的一条边移动到另一端。
  • 在树的全部顶点中等概率随机选取一个,并移动到该顶点。

输入格式

第一行两个正整数 n,qn,q,表示顶点数和询问数。

接下来 n−1n-1 行,每行两个正整数 x,yx,y,表示连接顶点 x,yx,y 的一条边。

接下来 qq 行,每行两个正整数 x,yx,y,表示从 xx 移动到 yy 的询问。

输出格式

输出 qq 行,每行一个实数,表示对应询问的最小期望步数。绝对误差不超过 10−610^{-6} 即视为正确。

样例

4 4
1 2
2 3
3 4
1 1
1 2
1 3
1 4
0.00000000
1.00000000
2.00000000
2.33333333

数据范围

  • 对于 20%20\% 的数据,n≤5n\le5,q≤10q\le10。
  • 对于 50%50\% 的数据,n≤1000n\le1000,q≤2000q\le2000。
  • 对于另外 20%20\% 的数据,树是一条链。
  • 对于所有数据,n≤100000n\le100000,q≤200000q\le200000,x,y≤nx,y\le n,且输入保证为合法的树。

原 PDF 题面