May Holidays
Contest: VK Cup 2018 - Round 3
Difficulty rating: 2900
Tags: data structures, trees

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.

Of 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).

Each 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.

In 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.

Input format:
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.

The 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.

The 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.

The 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.

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
7 8
4 5 1 1 5 5
0 0 0 1 2 0 0
2 6 3 7 -2 4 -3 1

Example output:
1 1 1 2 2 2 1 0

Example input:
5 6
1 2 3 4
4 0 0 1 0
1 5 2 3 -5 -1

Example output:
0 2 1 0 0 0

Editorial:
In terms of trees we have a rooted tree whose vertices may be activated and deactivated, and each vertex has a limit for the number of deactivated vertices among its descendants. We are required to switch the state of some vertex, and after each query we report the number of activated vertices unsatisfied vertices. Let the balance of a vertex be equal to the difference between its limit of deactivated descendants and the actual number of deactivated vertices among its descendants. In such terms we are interested in the number of activated vertices with the negative balance.
Let's utilize the idea of sqrt-optimization. Consider a block of $$$k$$$ consecutive queries, let us answer all of them. Suppose this query affects the state of vertices $$$v_1, v_2, \ldots, v_l$$$ ($$$l \leq k$$$), let us call such vertices interesting. Then, during the current query block, the balance will change only for the vertices that have at least one interesting vertex in its subtree.
Let's perform a classical trick of building the condensed tree containing the given interesting vertices. Namely, sort all the interesting vertices in order of their visit when doing DFS, and add all vertices of form $$$lca(v_i, v_{i+1})$$$ for all $$$1 \leq i < l$$$ to the set of interesting vertices. After such procedure all vertices whose balance may change may be splitted into $$$O(k)$$$ vertical paths each of which ends in an interesting vertex.
Now we are going to consider separately the interesting vertices and the interior vertices of all paths between interesting vertices. In each of the paths the balance of all vertices is changed simultaneously, thus we may sort all the vertices in each path by balance and then group all vertices having the same balance together. Introduce a pointer that initially stands at the first satisfied group (with non-negative balance). When the balance of all groups is changed by 1, instead of actually changing the value of balance we may just shift the pointer by at most one position to the left or to the right (artificially changing the origin) and accounting at most one group the pointer has passed in the answer.
On each query we have to perform such an operation with every path and interesting vertex that is located above the queried vertex. Since each vertex and each path is processed in $$$O(1)$$$, processing a single query takes $$$O(k)$$$ time and processing all queries inside a block takes $$$O(k^2)$$$ time. It is possible to build all paths and groups in running time of a single DFS plus sort time (std::sort or counting sort) for grouping vertices of equal balance. This part of solution takes $$$O(n)$$$ per each query block or $$$O(n \log n)$$$ depending on used sorting algorithm.
If we use count sort, the resulting complexity will be $$$O(\frac{m}{k} \left(k^2 + n\right))$$$, finally we can take $$$k = \Theta(\sqrt{n})$$$ and get $$$O(m \sqrt{n})$$$ running time.