配点 : 300 点
問題文
Yamamoto-kun 开发了一款名为 PackDrop 的软件,用于测试应用程序在通信环境较差的网络上的运行情况。 我们发明了一种以0.01 概率丢弃数据包的设备。
山本君 N 1 个设备的网络中必须安装多个 PackDrops,并且必须满足以下条件: 但是,我想尽量减少使用的 PackDrops 数量。
该网络中的每个设备都有 它的编号为 0 减去 N - 1 。 对于除
機器 0 之外的每个设备 有 1 父设备和设备 i 的父设备是设备 P_i 。设备 从 P_i 看到的设备 i 称为子设备。
具有直接父子关系的设备可以直接连接,也可以通过串联多个 PackDrop 进行连接。
父设备和子设备 当通过 n PackDrops 连接时,从父设备到子设备的数据包到达率为 0.99^n 。也就是说,直接连接时,数据包到达率为 1 。 对于
機器 x 来自设备 数据包到达 y 的到达率为 p、機器 y 来自设备 数据包到达 z 的到达率为 q 当设备 数据包到达 x 来自设备 数据包到达 z 的到达率为 p × q 。 对于
假设数据包传送速率不会由于 PackDrop 丢弃数据包以外的因素而发生变化。
没有子设备的设备 M 有一个,数量是 B_0, B_1, …, B_{M-1} 。每个 i ( 0 \leq i \leq N-1 ) 对于设备 来自 0 的设备 到达率 B_i 如果您想要 0.99^{C_i} ,请找到 PackDrops 的最小数量。
制約
- 2 \leq N \leq 1000
- 1 \leq M \leq N - 1
- 0 \leq P_i \leq i - 1
- 1 \leq B_i \leq N - 1
- 1 \leq C_i \leq 100000
- i \neq j 如果 B_i \neq B_j 是
- P_i = B_j 变为 i, j 不存在 如果不包含在
- 整数 k ( 1 \leq k \leq N-1 ) 上有 P_1, P_2, …, P_{N-1} 中 包含在 k 是 您也可以写 B_0, B_1, …, B_{M-1} 中
- N, M, P_i, B_i, C_i 是一个整数
入力
输入是按以下格式从标准输入给出的。
N M
P_1
:
P_{N-1}
B_0 C_0
:
B_{M-1} C_{M-1}
出力
输出 PackDrops 的最小数量。
入力例 1
3 2 0 0 1 5 2 10
出力例 1
15
将最少数量的 PackDrops 连接到该网络将如下图所示。
入力例 2
5 3 0 1 0 1 2 5 3 3 4 7
出力例 2
10
将最少数量的 PackDrops 连接到该网络将如下图所示。
入力例 3
7 4 0 0 2 2 3 3 1 3 4 2 5 8 6 6
出力例 3
11
将最少数量的 PackDrops 连接到该网络将如下图所示。