← 返回题目列表

AtCoder · tenka1_2016_qualA_b

B. 打包

中文机器翻译题面 查看原题

配点 : 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 连接到该网络将如下图所示。

サンプル 1

入力例 2

5 3
0
1
0
1
2 5
3 3
4 7

出力例 2

10

将最少数量的 PackDrops 连接到该网络将如下图所示。

サンプル 2

入力例 3

7 4
0
0
2
2
3
3
1 3
4 2
5 8
6 6

出力例 3

11

将最少数量的 PackDrops 连接到该网络将如下图所示。

サンプル 3