题目类型说明

这是一道提交函数题。你需要实现 init() 与 query()，不要编写 main 函数。

题目描述

国家 X 的地势完全平坦，但降雨只会落在一个非常小的区域里。不过该区域的降雨量很大。为了给全国供水，全国修建了一张由 N 个非常高（可视作无限高）的蓄水池构成的网络，其中有一些蓄水池之间通过水平直管道直接连接。任意两条管道的高度都不相同。

蓄水池从 1 到 N 编号，管道共有 M 条。对任意两个蓄水池，都存在一条由若干直管道组成的路径将它们连接起来。

每个蓄水池的底面积都是 1 m^2。因此，当某个蓄水池里有水时，水位每上升 1 毫米，就对应 1 升的水量。

设编号为 i 和 j 的两个蓄水池之间有一条直管道，其高度离地面为 p 毫米。若向蓄水池 i 中注水，那么当其中水量超过 p 升时（即水位超过 p 毫米），水就会通过这条管道流出，并开始流入蓄水池 j。

水在蓄水池之间的流动被视为瞬时发生，并且忽略管道直径，也就是说管道中不会存水。

发生降雨的区域只覆盖一个蓄水池，它的编号是 1。所有管道的高度都已知。

水务部想知道，国家中某些蓄水池最终会积多少水，因此需要一个程序来回答如下询问：

若落在蓄水池 1 所在区域的降雨量为 W 升/平方米，那么编号为 K 的蓄水池最终会积多少水？

其中 W 是整数，但答案可能是小数。若你的答案与标准答案的绝对误差不超过 10^{-4}，则视为正确。

请编写程序 rain 来回答这类询问。

实现细节

你的程序需要与评测器一起编译。

init() 的函数原型如下：

void init(int N, int M, int a[], int b[], long long c[]);

该函数会被调用一次，参数含义如下：

• N：蓄水池数量；
• M：管道数量；
• 对于每个 0 ≤ i < M，存在一条连接蓄水池 a[i] 与 b[i] 的管道，其高度为 c[i]。

query() 的函数原型如下：

double query(long long W, int K);

评测器会调用 Q 次 query()。参数含义如下：

• W：落入蓄水池 1 的水量；
• K：询问最终想知道积水量的蓄水池编号。

你需要提交一个名为 rain.cpp 的文件，其中包含 init() 和 query()，也可以包含其他辅助代码和函数，但不能包含 main() 函数。
你的文件开头必须写上：

#include "rain.h"

约束

• 1 ≤ N, M, Q ≤ 3 × 10^5
• 1 ≤ W, c_i ≤ 10^12
• 1 ≤ a_i, b_i, K ≤ N
• 任意两条管道高度均不相同

子任务

子任务的分数只有在该子任务下的所有测试点全部通过时才能获得。

子任务 6 的补充说明：在同一个测试中，后一个 query 调用的 W 值不会小于前一个调用的 W 值。

样例交互

设有 3 个蓄水池和 2 条管道：第一条连接 1 与 2，高度为 1；第二条连接 1 与 3，高度为 5。另外有 Q = 3 个询问。评测器会这样调用你的函数：

init(3, 2, {1, 1}, {2, 3}, {1, 5});

之后，评测器会调用三次 query()：

本地测试

题目提供了 rain.h 和 Lgrader.cpp，你可以把它们与你的程序一起编译，以便本地测试。

运行本地评测程序 Lgrader 时，输入格式如下：

• 第 1 行：N M
• 第 2 行：a_0 b_0 c_0
• 第 3 行：a_1 b_1 c_1
• …
• 第 M+1 行：a_{M-1} b_{M-1} c_{M-1}
• 第 M+2 行：Q
• 第 M+3 行：W_0 K_0
• 第 M+4 行：W_1 K_1
• …
• 第 M+2+Q 行：W_{Q-1} K_{Q-1}

如果你想以别的方式配置本地评测器，可以自由修改题目提供的文件。