CF925E May Holidays

在 Flatland 的五月，这个月有 $m$ 天。尽管五月假期早已取消，但某软件公司的员工们仍然习惯在五月休短假或长假。 当然，并不是所有的管理者都喜欢这样。公司有 $n$ 名员工，形成了一棵树状的上下级结构：每个员工都有一个唯一的整数编号 $i$，编号范围为 $1$ 到 $n$。除了编号为 $1$ 的总经理外，每个编号为 $i$ 的员工都有且仅有一位直接上级，编号为 $p_i$。这种上下级结构是无环的，也就是说，从任意员工出发，沿着直接上级不断向上，最终都会到达总经理。我们定义，如果 $v$ 是 $u$ 的直接上级，或者 $u$ 的直接上级是 $v$ 的下属，那么员工 $u$ 是员工 $v$ 的下属。令 $s_i$ 表示第 $i$ 位员工的下属人数（例如 $s_1 = n - 1$，因为除了他自己外，所有员工都是总经理的下属）。 每位员工 $i$ 有一个承受上限 $t_i$，这是一个介于 $0$ 到 $s_i$ 之间的整数，表示他最多能容忍同时有多少个下属休假。如果某一时刻，第 $i$ 位员工的下属中有超过 $t_i$ 人正在休假，并且他本人没有休假，那么他会感到不满。 在五月的 $m$ 天中，每天恰好发生一件如下两种事件之一：要么有一名员工在当天开始休假，要么有一名员工在当天开始结束休假。你知道这 $m$ 天内所有事件的顺序。你的任务是，对于每一天，计算当天公司内感到不满的员工人数。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 10^5$），分别表示公司员工数和五月的天数。 第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \leq p_i \leq n$），表示每位员工的直接上级编号。 第三行包含 $n$ 个整数 $t_1, t_2, \ldots, t_n$（$0 \leq t_i \leq s_i$），表示每位员工的承受上限。 第四行包含 $m$ 个整数 $q_1, q_2, \ldots, q_m$（$1 \leq |q_i| \leq n$，$q_i \ne 0$），表示每天发生的事件。如果 $q_i$ 为正，表示编号为 $q_i$ 的员工从这一天开始休假；如果 $q_i$ 为负，表示编号为 $-q_i$ 的员工从这一天开始结束休假。五月初时，没有任何员工在休假。保证每次休假和结束休假操作都是合法的，即某员工开始休假时他不在休假，结束休假时他正在休假。

输出 $m$ 个整数 $a_1, a_2, \ldots, a_m$，其中 $a_i$ 表示第 $i$ 天公司内感到不满的员工人数。

在第一个样例中，第 2 号员工在第一天开始休假后，总经理（编号 1）会感到不满，因为他不希望有任何下属休假。第四天，第 5 号员工会感到不满，因为他最后一名下属（编号 7）开始休假。第五天，第 2 号员工结束休假，但这不会影响不满员工人数，因为第 5 号和第 1 号员工仍然不满。第六天，第 3 号员工结束休假，使第 5 号员工不再不满。最后一天，总经理（编号 1）开始休假，公司内再无不满员工。 由 ChatGPT 4.1 翻译