Sắp đến mùa đông, nhân viên Bedao kéo nhau đi du lịch. Việc nghỉ đông này vốn không có gì to tát, nhưng nếu quá nhiều nhân viên nghỉ làm cùng lúc, một số lãnh đạo sẽ cảm thấy... bực bội.
Công ty Bedao có ~n~ nhân viên, và mỗi nhân viên ~i~ (trừ chủ tịch, người có số hiệu ~1~) sẽ có một cấp trên trực tiếp ~p_i~. Nói cách khác, cấu trúc của công ty Bedao có dạng cây. Nhân viên ~u~ là cấp dưới của nhân viên ~v~, nếu ~v~ là cấp trên trực tiếp của ~u~, hoặc cấp trên trực tiếp của ~u~ là cấp dưới của ~v~.
Gọi ~s_i~ là số nhân viên cấp dưới của nhân viên ~i~ (ví dụ, ~s_1 = n - 1~ vì tất cả các nhân viên đều là cấp dưới của chủ tịch). Mỗi nhân viên ~i~ cũng có sức chịu đựng ~t_i~: nếu tại một thời điểm nào đó, có nhiều hơn ~t_i~ cấp dưới của ~i~ nghỉ làm mà nhân viên ~i~ vẫn phải đi làm, ~i~ sẽ trở nên bực bội (và hạ lương của toàn bộ cấp dưới!)
Trong ~m~ ngày liên tục được ghi nhận ở công ty Bedao, mỗi ngày sẽ có ~1~ trong ~2~ sự kiện xảy ra: hoặc có một nhân viên nghỉ làm để đi du lịch, hoặc có một nhân viên trở về sau kì nghỉ. Ban đầu, không có nhân viên nào ở Bedao đang nghỉ làm. Hãy cho biết, vào ngày thứ ~i~, có bao nhiêu nhân viên trở nên bực bội vì quá nhiều cấp dưới nghỉ việc?
Input
Dòng đầu tiên chứa hai số nguyên dương ~n, m~ (~1 \le n, m \le 10^5~) — lần lượt là số nhân viên ở công ty Bedao, và số ngày được ghi nhận ở công ty.
Dòng thứ hai chứa ~n - 1~ số nguyên dương ~p_2, p_3, \ldots, p_n~ (~1 \le p_i \le n~) — số hiệu của cấp trên trực tiếp của nhân viên ~i~.
Dòng thứ ba chứa ~n~ số nguyên ~t_1, t_2, \ldots, t_n~ (~0 \le t_i \le s_i~) — sức chịu đựng của nhân viên thứ ~i~.
Dòng thứ tư chứa ~m~ số nguyên ~q_1, q_2, \ldots, q_m~ (~1 \le |q_i| \le n, q_i \neq 0~) — thể hiện sự kiện xảy ra trong ngày thứ ~i~. Nếu ~q_i > 0~, nhân viên ~q_i~ bắt đầu nghỉ làm để đi du lịch; nếu ~q_i < 0~, nhân viên ~-q_i~ trở về sau kì nghỉ của mình. Dữ liệu đảm bảo, một nhân viên chỉ có thể nghỉ làm khi đang đi làm ở công ty, và ngược lại.
Output
In ra ~m~ số nguyên ~c_1, c_2, \ldots, c_m~, với ~c_i~ là số nhân viên cảm thấy bực bội vào ngày thứ ~i~.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~20~ | ~n, m \le 5000~ |
2 | ~80~ | không có giới hạn gì thêm |
Sample Input 1
7 8
4 5 1 1 5 5
0 0 0 1 2 0 0
2 6 3 7 -2 4 -3 1
Sample Output 1
1
1
1
2
2
2
1
0
Bình luận