B - PackDrop 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300

問題文

ヤマモトくんは、通信環境の悪いネットワークでのアプリケーションの動作検証のために、PackDrop という、0.01 の確率でパケットを破棄する装置を発明しました。

ヤマモトくんは N 台の機器からなるネットワークに、いくつかのPackDropを取り付けて、以下の条件を満たす必要があります。ただし、使用する PackDrop の個数は最少にしたいです。

このネットワークの各機器には 0 から N - 1 の番号がふられています。

機器 0 以外の各機器には 1 台の親機器があり、機器 i の親機器は機器 P_i です。機器 P_i から見た機器 i を子機器といいます。

直接親子関係のある機器は直接つなぐか、PackDrop をいくつか直列にはさんでつなぐことができます。

親機器と子機器が n 個の PackDrop をはさんでつながっているとき、親機器から子機器へのパケットの到達率は 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} にしたいとき、最少の PackDrop の個数を求めてください。

制約

  • 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} に含まれないならば kB_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}

出力

最少の PackDrop の個数を出力せよ。


入力例 1

3 2
0
0
1 5
2 10

出力例 1

15

このネットワークに最少の PackDrop をつなぐと下図のようになります。

サンプル 1

入力例 2

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

出力例 2

10

このネットワークに最少の PackDrop をつなぐと下図のようになります。

サンプル 2

入力例 3

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

出力例 3

11

このネットワークに最少の PackDrop をつなぐと下図のようになります。

サンプル 3