O - Move to Rest
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
頂点 1 を根とする、N 頂点の根付き木があります。頂点 i (2 \le i \le N) の親は P_i です。頂点 1 には椅子が 10^{100} 個置いてあり、それ以外の頂点には椅子が 1 個ずつ置いてあります。それぞれの椅子には、人が 1 人まで座ることができます。
これから M 人の人たちが順番にこの木に休憩しに訪れます。i = 1, 2, \dots, M の順に、i 番目の人は以下の行動をとります。
- 頂点 A_i に訪れる。その後、空いている椅子がある頂点にたどり着くまで根の方向に向かって進む。空いている椅子がある頂点にたどり着いたら、その椅子に座り行動を終了する。
制約
- 入力は全て整数
- 1 \le N, M \le 10^6
- 1 \le P_i < i
- 1 \le A_i \le N
入力
入力は以下の形式で標準入力から与えられる。
N P_2 \ldots P_N M A_1 \ldots A_M
出力
答えを 1 行に出力せよ。
入力例 1
3 1 1 4 1 2 3 2
出力例 1
1
1 番目の人は頂点 1 から訪れて、そのまま頂点 1 の椅子に座ります。 2, 3 番目の人はそれぞれ頂点 2, 3 の椅子に座ります。 4 番目の人は頂点 2 を訪れますが、頂点 2 の椅子には既に 2 番目の人が座っているので頂点 1 に移動します。 頂点 1 の椅子は余っているので、その椅子に座り行動を終了します。
d_1 = d_2 = d_3 = 0, d_4 = 1 なので、出力すべき値は 1 です。
入力例 2
7 1 1 3 4 5 5 6 3 5 3 6 6 2
出力例 2
3