3738: happy
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：0
题目描述
给出一个n个节点的树，两点之间有且仅有一条路径相连。 给出m个点对xi,yi，如果添加一条双向边边{u,v}后xi和yi在一个简单环中，则称这条边是happy的，happy值为这个简单环的点数。 请你求出对于点对xi,yi，所有happy的边的happy值的平均数。
输入
第一行2个整数n,m；
接下来n-1行,每行两个整数x,y表示在树中x,y有一条双向边相连；
接下来m行,每行2个整数xi,yi表示询问点对。
输出
对于每个询问的点对，输出一个实数表示所有happy的边的happy值的平均数，结果保留7位小数。
样例输入 复制
4 3
2 4
4 1
3 2
3 1
2 3
4 1
样例输出 复制
4.0000000
3.0000000
3.0000000
提示
【样例输入2】
3 3
1 2
1 3
1 2
1 3
2 3
【样例输出2】
2.5000000
2.5000000
3.0000000
【样例解释】 在样例2中：对于第一个询问，边{1,2}和边{2,3}都是happy的，happy值分别为2,3，ans=(2+3)/2 对于第二个询问，边{1,3}和边{2,3}都是happy的，happy值分别为2,3，ans=(2+3)/2 对于第三个询问，只有边{2,3}是happy的，happy值为3，ans=3/1
【数据范围】
对于20%的数据满足：n<=100,m<=100；
对于100%的数据满足：n<=100000,m<=100000。