May Holidays

Flatland에서는 It's May이며, 이번 달은 m일이다. May Holidays이 오래전에 폐지되었음에도 불구하고, 어떤 소프트웨어 회사의 직원들은 여전히 오월에 짧거나 긴 휴가를 떠나는 습관이 있다.

물론 회사의 모든 관리자가 이를 좋아하는 것은 아니다. 회사에는 n명의 직원이 있으며, 이들은 트리 형태의 상하 관계를 이룬다. 각 직원은 1부터 n 사이의 서로 다른 정수 ID i를 가지며, ID가 i인 각 직원은(ID가 1인 최고 관리자는 제외) ID가 $p_i$인 직속 관리자를 정확히 한 명 가진다. 상하 관계에는 사이클이 없다. 즉, 임의의 직원에서 시작하여 그 직원의 직속 관리자로 계속 이동하면 결국 최고 관리자에게 도달한다. v가 u의 직속 관리자이거나, u의 직속 관리자가 v의 부하 직원이라면 직원 u를 직원 v의 부하 직원이라고 정의한다. i-th번째 직원이 가진 부하 직원의 수를 $s_i$라고 하자 (for example, $s_1$ = n - 1, because all employees except himself are subordinates of the head manager).

각 직원 i에게는 0부터 $s_i$ 사이의 정수인 인내 한도 $t_i$가 있다. 이는 i-th번째 직원이 견딜 수 있는, 동시에 휴가 중인 자신의 부하 직원 수의 최댓값을 나타낸다. 어느 순간 i-th번째 직원의 부하 직원 중 휴가 중인 사람이 $t_i$명보다 엄격히 많고, i-th번째 직원 자신은 휴가 중이 아니라면, 그 직원은 불쾌해진다.

오월의 m일 각각에는 다음 두 가지 유형의 사건 중 정확히 하나가 일어난다. 한 직원이 그날이 시작될 때 휴가를 떠나거나, 한 직원이 그날이 시작될 때 휴가에서 돌아온다. 앞으로 m일 동안 일어날 사건의 순서를 알고 있다. 각 m일에 대해 그날 불쾌한 직원의 수를 계산해야 한다.

첫째 줄에 두 정수 n와 m (2 ≤ n, m ≤ $10^5$)가 주어진다. 각각 회사의 직원 수와 오월의 날짜 수를 나타낸다.

둘째 줄에는 직원들의 직속 관리자를 나타내는 n - 1개의 정수 $p_2$, $p_3$, …, $p_n$ (1 ≤ $p_i$ ≤ n)가 주어진다.

셋째 줄에는 직원들의 인내 한도를 나타내는 n개의 정수 $t_1$, $t_2$, …, $t_n$ (0 ≤ $t_i$ ≤ $s_i$)가 주어진다.

넷째 줄에는 사건을 나타내는 m개의 정수 $q_1$, $q_2$, …, $q_m$ (1 ≤ |$q_i$| ≤ n, $q_i$ ≠ 0)가 주어진다. $q_i$가 양수이면 ID가 $q_i$인 직원이 이날부터 휴가를 떠나고, $q_i$가 음수이면 직원 -$q_i$가 이날부터 휴가에서 돌아온다. 오월이 시작될 때는 휴가 중인 직원이 없다. 어떤 직원이 휴가를 떠날 때는 그 순간 휴가 중이 아니며, 그 반대의 경우도 마찬가지임이 보장된다.

m개의 정수로 이루어진 수열 $a_1$, $a_2$, …, $a_m$을 출력한다. 여기서 $a_i$는 i-th번째 날에 불쾌한 직원의 수이다.

첫 번째 예제에서 첫날 ID가 2인 직원이 휴가를 떠난 후, 자신의 부하 직원 중 누구도 휴가를 떠나는 것을 원하지 않는 ID가 1인 최고 관리자가 불쾌해진다. 넷째 날에는 마지막으로 남아 있던 직원인 ID가 7인 직원이 휴가를 떠나므로 ID가 5인 직원이 불쾌해진다. 다섯째 날에는 ID가 2인 직원이 휴가에서 돌아오지만, 직원 5와 1은 여전히 불쾌하므로 불쾌한 직원의 수에는 영향을 주지 않는다. 여섯째 날에는 ID가 3인 직원이 휴가에서 돌아와 ID가 5인 직원이 불쾌해지는 것을 막으며, 마지막 날에는 ID가 1인 최고 관리자가 휴가를 떠나 회사에 불쾌한 사람이 전혀 남지 않게 된다.