{"raw_statement":[{"iden":"statement","content":"It's May in Flatland, and there are $m$ days in this month. Despite the fact that May Holidays are canceled long time ago, employees of some software company still have a habit of taking short or long vacations in May.\n\nOf course, not all managers of the company like this. There are $n$ employees in the company that form a tree-like structure of subordination: each employee has a unique integer id $i$ between $1$ and $n$, and each employee with id $i$ (except the head manager whose id is 1) has exactly one direct manager with id $p_i$. The structure of subordination is not cyclic, i.e. if we start moving from any employee to his direct manager, then we will eventually reach the head manager. We define that an employee $u$ is a subordinate of an employee $v$, if $v$ is a direct manager of $u$, or the direct manager of $u$ is a subordinate of $v$. Let $s_i$ be the number of subordinates the $i$\\-th employee has (for example, $s_1 = n - 1$, because all employees except himself are subordinates of the head manager).\n\nEach employee $i$ has a bearing limit of $t_i$, which is an integer between $0$ and $s_i$. It denotes the maximum number of the subordinates of the $i$\\-th employee being on vacation at the same moment that he can bear. If at some moment strictly more than $t_i$ subordinates of the $i$\\-th employee are on vacation, and the $i$\\-th employee himself is not on a vacation, he becomes _displeased_.\n\nIn each of the $m$ days of May exactly one event of the following two types happens: either one employee leaves on a vacation at the beginning of the day, or one employee returns from a vacation in the beginning of the day. You know the sequence of events in the following $m$ days. Your task is to compute for each of the $m$ days the number of displeased employees on that day."},{"iden":"input","content":"The first line contains two integers $n$ and $m$ ($2 \\leq n, m \\leq 10^5$) — the number of employees in the company and the number of days in May.\n\nThe second line contains $n - 1$ integers $p_2, p_3, \\ldots, p_n$ ($1 \\leq p_i \\leq n$), denoting the direct managers of employees.\n\nThe third line contains $n$ integers $t_1, t_2, \\ldots, t_n$ ($0 \\leq t_i \\leq s_i$), denoting the bearing limits of empoyees.\n\nThe fourth line contains $m$ integers $q_1, q_2, \\ldots, q_m$ ($1 \\leq |q_i| \\leq n$, $q_i \\ne 0$), denoting the events. If $q_i$ is positive, then the employee with id $q_i$ leaves for a vacation starting from this day, if $q_i$ is negative, then the employee $-q_i$ returns from a vacation starting from this day. In the beginning of May no employee is on vacation. It is guaranteed that if some employee leaves for a vacation, he is not on a vacation at the moment and vice versa."},{"iden":"output","content":"Print a sequence of $m$ integers $a_1, a_2, \\ldots, a_m$, where $a_i$ is the number of displeased employees on the $i$\\-th day."},{"iden":"examples","content":"Input\n\n7 8\n4 5 1 1 5 5\n0 0 0 1 2 0 0\n2 6 3 7 -2 4 -3 1\n\nOutput\n\n1 1 1 2 2 2 1 0\n\nInput\n\n5 6\n1 2 3 4\n4 0 0 1 0\n1 5 2 3 -5 -1\n\nOutput\n\n0 2 1 0 0 0"},{"iden":"note","content":"In the first sample test after employee with id 2 leaves for a vacation at the first day, the head manager with id 1 becomes displeased as he does not want any of his subordinates to go for a vacation. At the fourth day employee with id 5 becomes displeased as his last remaining employee with id 7 leaves for a vacation. At the fifth day employee with id 2 returns from the vacation, but it does not affect the number of displeased employees as the employees 5 and 1 are still displeased. At the sixth day employee with id 3 returns back from the vacation, preventing the employee with id 5 from being displeased and at the last day the head manager with id 1 leaves for a vacation, leaving the company without the displeased people at all."}],"translated_statement":[{"iden":"statement","content":"现在是扁平国的五月，这个月有 $m$ 天。尽管五一假期早已被取消，但某软件公司的员工仍保留着在五月休短假或长假的习惯。\n\n当然，并非公司所有管理者都喜欢这样。公司共有 $n$ 名员工，形成了一种树状的隶属结构：每位员工都有一个唯一的整数编号 $i$（范围在 $1$ 到 $n$ 之间），每个编号为 $i$ 的员工（除了编号为 1 的首席经理）恰好有一位直接上级，其编号为 $p_i$。隶属结构无环，即从任意员工开始不断向上追溯其直接上级，最终一定会到达首席经理。我们定义：员工 $u$ 是员工 $v$ 的下属，当且仅当 $v$ 是 $u$ 的直接上级，或 $u$ 的直接上级是 $v$ 的下属。记 $s_i$ 为第 $i$ 位员工的下属数量（例如，$s_1 = n -1$，因为除他自己外的所有员工都是首席经理的下属）。\n\n每位员工 $i$ 有一个承受上限 $t_i$，是一个介于 $0$ 和 $s_i$ 之间的整数，表示他能容忍的同时休假的下属的最大数量。如果在某一时刻，员工 $i$ 的下属中恰好有超过 $t_i$ 人正在休假，且员工 $i$ 本人并未休假，则他将变得 _不满_。\n\n在五月的 $m$ 天中，每天恰好发生以下两种事件之一：要么某位员工在当天开始时开始休假，要么某位员工在当天开始时结束休假返回公司。你已知接下来 $m$ 天的事件序列。你的任务是计算每一天中不满员工的数量。\n\n第一行包含两个整数 $n$ 和 $m$（$2 \\leq n, m \\leq 10^5$）——公司员工数量和五月的天数。\n\n第二行包含 $n -1$ 个整数 $p_2, p_3, \\dots, p_n$（$1 \\leq p_i \\leq n$），表示每位员工的直接上级。\n\n第三行包含 $n$ 个整数 $t_1, t_2, \\dots, t_n$（$0 \\leq t_i \\leq s_i$），表示每位员工的承受上限。\n\n第四行包含 $m$ 个整数 $q_1, q_2, \\dots, q_m$（$1 \\leq |q_i| \\leq n$，$q_i \\neq 0$），表示事件。若 $q_i$ 为正，则编号为 $q_i$ 的员工从当天开始休假；若 $q_i$ 为负，则编号为 $-q_i$ 的员工从当天开始结束休假返回公司。五月开始时没有任何员工在休假。保证若某员工开始休假，则他当前未休假，反之亦然。\n\n请输出一个长度为 $m$ 的整数序列 $a_1, a_2, \\dots, a_m$，其中 $a_i$ 表示第 $i$ 天不满员工的数量。\n\n在第一个样例中，第一天员工 2 开始休假后，首席经理（编号 1）变得不满，因为他不希望任何下属休假。第四天，员工 5 变得不满，因为他的最后一个仍在岗的下属（编号 7）也开始休假。第五天，员工 2 结束休假返回，但并未改变不满员工数量，因为员工 5 和 1 仍处于不满状态。第六天，员工 3 结束休假返回，使员工 5 不再不满；最后一天，首席经理（编号 1）开始休假，公司中不再有任何不满员工。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $m$（$2 \\leq n, m \\leq 10^5$）——公司员工数量和五月的天数。第二行包含 $n -1$ 个整数 $p_2, p_3, \\dots, p_n$（$1 \\leq p_i \\leq n$），表示每位员工的直接上级。第三行包含 $n$ 个整数 $t_1, t_2, \\dots, t_n$（$0 \\leq t_i \\leq s_i$），表示每位员工的承受上限。第四行包含 $m$ 个整数 $q_1, q_2, \\dots, q_m$（$1 \\leq |q_i| \\leq n$，$q_i \\neq 0$），表示事件。若 $q_i$ 为正，则编号为 $q_i$ 的员工从当天开始休假；若 $q_i$ 为负，则编号为 $-q_i$ 的员工从当天开始结束休假返回公司。五月开始时没有任何员工在休假。保证若某员工开始休假，则他当前未休假，反之亦然。"},{"iden":"output","content":"请输出一个长度为 $m$ 的整数序列 $a_1, a_2, \\dots, a_m$，其中 $a_i$ 表示第 $i$ 天不满员工的数量。"},{"iden":"examples","content":"输入\n7 8\n4 5 1 1 5 5\n0 0 0 1 2 0 0\n2 6 3 7 -2 4 -3 1\n输出\n1 1 1 2 2 2 1 0\n\n输入\n5 6\n1 2 3 4\n4 0 0 1 0\n1 5 2 3 -5 -1\n输出\n0 2 1 0 0 0"},{"iden":"note","content":"在第一个样例中，第一天员工 2 开始休假后，首席经理（编号 1）变得不满，因为他不希望任何下属休假。第四天，员工 5 变得不满，因为他的最后一个仍在岗的下属（编号 7）也开始休假。第五天，员工 2 结束休假返回，但并未改变不满员工数量，因为员工 5 和 1 仍处于不满状态。第六天，员工 3 结束休假返回，使员工 5 不再不满；最后一天，首席经理（编号 1）开始休假，公司中不再有任何不满员工。"}],"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}