分数: 300 分
问题陈述
高桥正在对山区进行地形模拟。
山区有 N 位置,每个编号自 1 to N。地点 i 的海拔为 H_i 并且最初成立 W_i 升雨水。
这些位置通过以下方式连接 M 频道。的 j第通道双向连接位置 U_j 和位置 V_j。水只从海拔较高的地方流向海拔较低的地方。也就是说,如果由通道连接的两个位置具有相同的高度,则水不会流过该通道。
对于一个位置 v,在直接连接到的位置中 v 通过通道,海拔严格低于 v 被称为 下游邻居 of v.
高桥已在 K 位置(如果 K = 0,没有安装水坝)。大坝安装的位置都有编号 S_1, S_2, \ldots, S_K。在建有水坝的地方,水可以从其他地方通过渠道流入,但水不会从该地方流出。
各地点的出水按以下程序处理:
- 按海拔降序对所有位置进行排序。由于水不会在相同高程的位置之间流动,因此具有相同高程的位置之间的排序是任意的(结果不取决于处理顺序)。
- 按此顺序一一处理每个位置。让 v 是正在处理的位置,并让 w 升 是当前累积的水量 v.
- 如果大坝安装在 v:什么都不做。全部 w 升水仍处于 v.
- 如果没有安装大坝 v,并且有 d 下游邻居(d \geq 1):全部 w 升水 v 流出。流出的水平均分配给 d 下游邻居,每个下游邻居接收 \frac{w}{d} 升水(即使下游邻居安装了水坝,水也会流入)。出水后水量为 v 变为 0.
- 如果没有安装大坝 v,并且没有下游邻居 (包括没有连接通道的孤立位置,或者所有连接位置的标高都大于或等于 v): 水保持在 v 原样。
当水在某个位置的流出处理期间流入下游邻居时,该水立即聚集在下游邻居处,并在该下游邻居本身被处理时被集中处理。
所有流出处理完成后,确定每个位置的剩余水量。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
- 最多有一个通道连接同一对位置(无多边)
- 1 \leq S_k \leq N (1 \leq k \leq K)
- S_1, S_2, \ldots, S_K 都是不同的
- 所有输入值均为整数
输入
N M K H_1 H_2 \ldots H_N W_1 W_2 \ldots W_N U_1 V_1 U_2 V_2 \vdots U_M V_M S_1 S_2 \ldots S_K
- 第一行包含位置数 N,通道数 M,以及有水坝的地点数量 K,以空格分隔。
- 第二行包含标高 每个位置的 H_1, H_2, \ldots, H_N ,以空格分隔。
- 第三行包含初始水量 W_1, W_2, \ldots, W_N ,以空格分隔。
- 以下 M 行包含频道信息。的 j- 这些行(行 整个输入的 3 + j 包含位置 U_j 和 V_j 由 j第一个通道,以空格分隔。
- If K \geq 1,最后一行包含位置编号 S_1, S_2, \ldots, S_K 安装水坝的地方,以空格分隔。如果 K = 0,该行不存在。
输出
输出所有流出处理完成后每个位置的水量,从位置 1 到位置 N,单行上用空格分隔。由于平均分配可能会导致非整数水量,因此小数输出是可以接受的。对于每个输出值,如果与真实值的绝对误差最多为 10^{-6},或者如果真值非零且相对误差至多 10^{-6}.
示例输入 1
4 4 0 10 20 5 5 0 12 0 0 1 2 1 3 2 3 2 4
示例输出 1
0.0000000000 0.0000000000 8.0000000000 4.0000000000
示例输入 2
3 2 1 30 20 10 6 0 0 1 2 2 3 2
示例输出 2
0.0000000000 6.0000000000 0.0000000000
示例输入 3
6 7 1 50 40 40 30 20 10 18 6 0 0 0 0 1 2 1 3 2 4 2 5 3 5 4 6 5 6 5
示例输出 3
0.0000000000 0.0000000000 0.0000000000 0.0000000000 16.5000000000 7.5000000000
示例输入 4
8 10 2 100 80 80 60 50 50 30 10 24 0 0 0 12 0 0 0 1 2 1 3 2 4 3 4 3 5 4 6 4 7 5 7 6 8 7 8 4 6
示例输出 4
0.0000000000 0.0000000000 0.0000000000 18.0000000000 0.0000000000 0.0000000000 0.0000000000 18.0000000000
示例输入 5
1 0 0 1000000000 999999999
示例输出 5
999999999.0000000000