← 返回题目列表

Codeforces · 925/E

E. 五月假期

中文机器翻译题面 查看原题

现在是 Flatland 的五月,这个月有 $$$m$$$ 天。尽管五一假期早已取消,但一些软件公司的员工仍然有在五月放短假或长假的习惯。

当然,并不是所有公司的管理者都这样。公司中有 $$$n$$$ 名员工,形成树状隶属结构:每个员工在 $$$1$$$ 到 $$$n$$$ 之间都有一个唯一的整数 id $$$i$$$,并且每个 id $$$i$$$ 的员工(id 为 1 的主管除外)恰好有一个 id $$$p_i$$$ 的直属经理。隶属结构不是循环的,也就是说,如果我们开始从任何员工转移到他的直接经理,那么我们最终将到达主管经理。我们定义员工$$$u$$$是员工$$$v$$$的下属,如果$$$v$$$是$$$u$$$的直接经理,或者$$$u$$$的直接经理是$$$v$$$的下属。令 $$$s_i$$$ 为第 $$$i$$$ 个员工的下属数量(例如,$$$s_1 = n - 1$$$,因为除了他自己之外的所有员工都是主管的下属)。

每个员工$$$i$$$ 的轴承限额为$$$t_i$$$,它是$$$0$$$ 和$$$s_i$$$ 之间的整数。表示第$$$i$$$员工所能承受的同时休假的下属人数上限。如果在某个时刻,第 $$$i$$$ 个员工的严格超过 $$$t_i$$$ 下属正在休假,而第 $$$i$$$ 个员工本人没有休假,他就会感到不高兴。

在五月的每一天中,都会发生以下两种类型的事件:一名员工在当天开始休假,或者一名员工在当天开始休假返回。您知道接下来 $$$m$$$ 天内事件的顺序。您的任务是计算每一 $$$m$$$ 天当天不满意的员工数量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n, m \leq 10^5$$$) — 公司的员工人数和 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$$$为正数,则ID为$$$q_i$$$的员工从这一天开始休假,如果$$$q_i$$$为负数,则员工$$$-q_i$$$从这一天开始休假返回。五月初,没有员工休假。可以保证,如果某个员工去休假,他目前不在休假,反之亦然。

输出

打印一系列 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$,其中 $$$a_i$$$ 是第 $$$i$$$ 天不满意的员工数量。

示例

输入 #1

7 8
4 5 1 1 5 5
0 0 0 1 2 0 0
2 6 3 7 -2 4 -3 1

输出 #1

1 1 1 2 2 2 1 0

输入 #2

5 6
1 2 3 4
4 0 0 1 0
1 5 2 3 -5 -1

输出 #2

0 2 1 0 0 0

注意

在id为2的员工第一天请假后的第一个样本测试中,id为1的主管感到不高兴,因为他不想让任何下属去休假。第四天,ID 5 的员工变得不高兴,因为他最后一个 id 7 的员工离开去度假。第五天,id 为 2 的员工休假回来,但这并不影响不满员工的数量,因为员工 5 和 1 仍然不满。第六天,id 3的员工休假回来,避免了id 5的员工不高兴,而最后一天,id 1的主管去度假,离开公司,没有不高兴的人。