1734. [CF 123E]树状迷宫

【题目描述】

一个迷宫是一棵树（即一张无向图，其中任意两点之间仅有一条路径）。迷宫的起点和终点都按照某种概率随机选取。人们会在迷宫中用深度优先搜索的方法搜寻终点。如果有许多条可能的路径，会等概率地选取一条。考虑如下伪代码：

DFS(x)
    if x == exit vertex then
        finish search
    flag[x] <- TRUE
    // here all permutations have equal probability to be chosen
    random shuffle the vertices' order in V(x) 
    for i <- 1 to length[V] do
        if flag[V[i]] = FALSE then
            count++;
            DFS(y);
    count++;

$V(x)$ 是和 $x$ 相邻的顶点列表。最初 $flag$ 数组的值均为 $false$。第一次 $DFS$ 的参数是迷宫的入口节点。当搜索终止，变量 $count$ 的值就是在迷宫中走的步数。

你的任务是计算在迷宫中从入口到出口，所走的期望步数。

【输入格式】

输入文件的第一行是图的顶点数 $n(1 \leq n \leq 10^5)$。接下来 $n-1$ 行每行有一对整数 $a_i$ 和 $b_i$，代表顶点 $a_i$ 和 $b_i$ 之间有一条边 $(1 \leq a_i,b_i \leq n)$。保证所给的图是一棵树。

接下来的 $n$ 行每行有两个非负整数 $x_i,y_i$，起点 $i$ 被选为入口的概率是 $x_i/∑x_i$，被选为出口的概率是 $y_i/∑y_i$。$∑x_i$ 和 $∑y_i$ 都不超过 $10^6$。

【输出格式】

输出一行一个实数，即步数的期望值。你程序输出与标准输出的相对误差不能超过 $10^{-9}$。

【样例输入】

样例输入1：
2
1 2
0 1
1 0

样例输入2：
3
1 2
1 3
1 0
0 2
0 3

样例输入3：
7
1 2
1 3
2 4
2 5
3 6
3 7
1 1
1 1
1 1
1 1
1 1
1 1
1 1

【样例输出】

样例输出1：
1.00000000000000000000

样例输出2：
2.00000000000000000000

样例输出3：
4.04081632653

【提示】

在第一组样例中，入口总是 $1$，出口总是 $2$.

在第二组样例中，入口总是 $1$，出口有 $2/5$ 的可能性是 $1$，有 $3/5$ 的可能性是 $3$.无论出口是 $2$ 或 $3$，步数的期望值都是相等的（因为图是对称的）。第一步有 $0.5$ 的概率走到出口，有 $0.5$ 的概率走到另一个节点。对于第一种情况，步数是 $1$，对于第二种情况步数是 $3$.因此步数的数学期望就是 $2/5*(1*0.5+3*0.5)+3/5*(1*0.5+3*0.5)$。

【来源】

CODEFORCES 123E