深入探索泡泡乌托邦 - المسألة

在神秘的水下国度 Bubbletopia 中，城市建在由闪烁通道相连的巨大气泡中。这些气泡编号为 $1$ 到 $N$，形成了一个以大气泡（Grand Bubble）$1$ 为根的宏伟树形结构。Bubbletopia 的居民和谐地生活在一起，每个气泡 $i$ 庇护着 $P_i$ 名居民。

气泡之间由 $N - 1$ 条通道连接，允许人们从任意一个气泡到达另一个气泡。居民们通过这些通道旅行，探索他们世界的深处。

某天，皇室发现王位继承人失踪了！最后的目击记录显示，继承人就在以气泡 $X$ 为根的子树深处的某个地方。以气泡 $X$ 为根的子树包括气泡 $X$ 以及从 $X$ 出发远离大气泡 $1$ 所能到达的所有气泡。时间紧迫，皇家卫队必须迅速行动。

作为安全主管，你被分配了 $K$ 支精英搜救队。每支队伍都可以从气泡 $X$ 出发开始任务，沿着远离大气泡的任何路径移动。每次任务都包括移动通过一系列气泡，沿途检查每个气泡中的居民以寻找继承人。

你的任务是制定一种搜救策略，利用这 $K$ 支搜救队最大化找到继承人的概率。在搜救过程中，继承人会一直留在同一个气泡中。

由于继承人可能躲在任何地方，他们是该子树内任何一名居民的概率是均等的。因此，继承人在某个特定气泡中的概率与该气泡中的居民人数成正比。

请注意，多次访问同一个气泡并不会增加找到继承人的几率，因为在搜救期间他们不会在气泡之间移动。

共有 $Q$ 个这样的场景。每个场景都是独立的，对于每个场景，你会得到搜救的起点气泡 $X$ 和可用的搜救队数量 $K$。你能计算出在每个场景中，使用最优搜救策略找到继承人的最高概率吗？

第一行包含两个整数 $N$ 和 $Q$：气泡的数量和场景的数量（$1 \le N, Q \le 3 \cdot 10^5$）。

第二行包含 $N$ 个整数 $P_1, P_2, \dots, P_N$：每个气泡中的居民人数（$1 \le P_i \le 10^6$）。

接下来的 $N - 1$ 行，每行包含两个整数 $U$ 和 $V$：由通道连接的两个节点（$1 \le U, V \le N, U \neq V$）。保证生成的图是一棵树：连通且不含环、自环或重边。

接下来的 $Q$ 行，每行包含两个整数 $X$ 和 $K$：搜救的起点气泡和可用的搜救队数量（$1 \le X, K \le N$）。

对于每个场景，输出一个介于 $0$ 和 $1$ 之间的实数，表示使用最优搜救路径找到继承人的最高概率。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

6 6
1 10 10 10 5 6
5 6
1 2
3 2
5 1
2 4
1 1
1 2
1 3
2 2
5 1
4 6

0.5000000000
0.7619047619
1.0000000000
1.0000000000
1.0000000000
1.0000000000

以下是样例的解释。

在第一个场景中，可以将一支搜救队派往路径 $1 \to 2 \to 3$，在树中居住的 $42$ 人中总共搜寻 $21$ 人，使得找到继承人的概率等于 $50\%$。
在第二个场景中，可以将一支搜救队派往路径 $1 \to 2 \to 3$，而第二支队伍派往路径 $1 \to 5 \to 6$，在树中居住的 $42$ 人中总共搜寻 $32$ 人，使得找到继承人的概率约为 $76\%$。
在第三个场景中，使用 $3$ 支搜救队可以搜寻所有 $42$ 人。
在第四个场景中，使用 $2$ 支搜救队可以搜寻所有 $30$ 人。
在第五个场景中，使用提供的一支搜救队可以搜寻所有 $11$ 人。
在第六个场景中，使用单支搜救队即可搜寻所有 $10$ 人，其余 $5$ 支搜救队无事可做。

QOJ.ac