sweets — EJOI contest
Task type: batch | Time limit: 3 s | Memory limit: 256 MB | Difficulty: 20
Algorithms: euler tour, data structures, tree, segment tree, binary search

![EJOI 2024 Day 2 Sweets](_page_0_Picture_0.jpeg)

# Sweets

Sandu graduated from high school and decided to pursue his passion as a candy salesperson.

Balti, a city in Moldova, has *N* markets, which are connected with streets between them. The marketplace has an interesting structure. Each market can be accessed from any other market by traveling through some number of streets, and there are exactly *N* − 1 streets. Also, Sandu is currently staying at market 1. So, the markets form a rooted tree structure where market 1 is the root.

Additionally, each market *i* has a toughness level *t<sub>i</sub>* and a learning level *l<sub>i</sub>*. Initially the learning level of each market is 0, and Sandu has a selling skill level of 0.

When Sandu visits market *i*, his selling skill level increases by *l<sub>i</sub>*. Sandu has success at market *i* if his selling skill level is at least *t<sub>i</sub>* (the market's toughness level). Note that Sandu's selling skill level increases as soon as he enters the market *i*, regardless of whether he was successful or not. This means his selling skill level increases before trying to do anything inside the market.

Also, as Balti is a really busy city, on each of the following *Q* days there will be an event happening. On day *j*, event *j* will happen. An event is described by two **positive** integers - *u<sub>j</sub>* and *x<sub>j</sub>* meaning that on day *j*, there will be an event at the market *u<sub>j</sub>* and the learning level for the corresponding market will be **permanently** increased by *x<sub>j</sub>*. In other words, event *j* means that on day *j* the learning level will be increased by *x<sub>j</sub>* (*l<sub>uj</sub> := l<sub>uj</sub> + x<sub>j</sub>*).

Sandu plans to visit some markets and sell candies in them. He will pick some market *k* and will visit all markets on the path from the first market to market *k*, in that order. Sandu wants to succeed at as many markets as possible. He will continue his journey towards market *k* regardless of whether he was successful or not. Additionally, every day, Sandu starts at market 1 and his selling skill level resets, starting each day with a selling skill level of 0.

For each day *j*, help Sandu find the largest number of markets he can be successful at, if he optimally picks the location of the final market of that day.

#### Input

The first line of input contains two integers *N* and *Q* (1 ≤ *N*, *Q* ≤ 5 ⋅ 10<sup>5</sup>).

The second line contains *N* − 1 integers that represent the rooted tree structure of the markets: *p<sub>2</sub>*,..., *p<sub>N</sub>*, meaning that there exists an edge between *p<sub>i</sub>* and *i*, and *p<sub>i</sub>* is the parent of *i*.

Additionally for each *i*, the condition 1 ≤ *p<sub>i</sub>* < *i* is always satisfied.

The third line contains *N* integers: *t<sub>1</sub>*, *t<sub>2</sub>*, ..., *t<sub>N</sub>* (0 ≤ *t<sub>i</sub>* ≤ 10<sup>9</sup>) — the toughness level of the given markets.

Then, *Q* lines follow, representing the events happening on day *j* = 1, 2,...,*Q*.

Line *j* contains two integers — *u<sub>j</sub>* and *x<sub>j</sub>* describing the event for *j*-th day (1 ≤ *u<sub>j</sub>* ≤ *N*, 1 ≤ *x<sub>j</sub>* ≤ 10<sup>9</sup>).

#### Output

Output *Q* lines - in the *j*-th line you should output the answer for *j*-th day.

### Examples

| Input                                                                                                                                 | Output                |
| :------------------------------------------------------------------------------------------------------------------------------------ | :-------------------- |
| 12 5<br>1 1 3 3 1 6 7 1 9 10 11<br>1 2 6 3 5 4 6 5 2 3 4 5<br>1 1<br>1 1<br>3 2<br>6 3<br>9 6                                      | 1<br>2<br>2<br>3<br>5 |
| 5 4<br>1 2 3 4<br>1 2 5 6 7<br>1 1<br>1 2<br>1 1<br>1 2                                                                           | 1<br>2<br>2<br>4      |
| 5 5<br>1 1 1 1<br>1 2 3 4 5<br>4 4<br>2 2<br>5 5<br>1 1<br>3 3                                                                     | 1<br>1<br>1<br>2<br>2 |

The initial tree for the first example looks like this. In the image the numbers to the right of a market represent the learning level of that market, and the numbers to the left of the market represent the toughness level of the corresponding market.

![Initial Tree](_page_2_Figure_1.jpeg)

After the first day, the tree changes in the following way, and one of the possible optimal markets Sandu could go to is 6, obtaining a maximum answer of 1 since the learning level of market 1 is at least equal to its toughness level which is also 1.

![Tree after first day](_page_2_Figure_3.jpeg)

After the second event, the answer changes to 2 since Sandu can choose to go to market 2, obtaining a selling skill level of 2 from market 1, which is greater or equal to both toughness levels of market 1 and 2.

![Tree after second event](_page_3_Figure_0.jpeg)

After the third event, the answer doesn't change but the tree changes in the way shown below:

![Tree after third event](_page_3_Figure_2.jpeg)

After the fourth event, the answer changes to 3, since if Sandu starts at market 1, he improves his selling skill level to 2, meaning he is successful at market 1. Afterwards, he moves to market 6, where he improves his selling skill level to 5, meaning he is also successful in market 6 as well. Then, he moves to market 7 where he has no success, and then he moves to market 8, where he is successful since 5 ≥ 5.

![Tree after fourth event](_page_3_Figure_4.jpeg)

For the last event, the tree changes in the following way and the optimal answer is 5, since Sandu can go to market 12 and he will be successful at markets 1, 9, 10, 11, 12.

![Tree after last event](_page_4_Figure_0.jpeg)

## Constraints and Scoring

- 1 ≤ *N*, *Q* ≤ 5 ⋅ 10<sup>5</sup>.
- 1 ≤ *p<sub>i</sub>* < *i* is always satisfied.
- 0 ≤ *t<sub>i</sub>* ≤ 10<sup>9</sup> for all *i* (1 ≤ *i* ≤ *N*).
- 1 ≤ *u<sub>j</sub>* ≤ *N* for all *j* (1 ≤ *j* ≤ *Q*).
- 1 ≤ *x<sub>j</sub>* ≤ 10<sup>9</sup> for all *j* (1 ≤ *j* ≤ *Q*).

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

| Group | Score | Limits                                                                     |
| :---- | :---- | :------------------------------------------------------------------------- |
| 1     | 7     | \(p_i = 1 \text{ for } 1 < i \le N, \text{ and } N, Q \le 2000.\)          |
| 2     | 8     | \(N, Q \le 2000\) , tree structure respects \(p_i = i - 1 \text{ for all } i\) |
| 3     | 17    | Tree structure respects \(p_i = i - 1 \text{ for } 1 < i \le N\)           |
| 4     | 12    | \(N, Q \le 2000\)                                                         |
| 5     | 21    | \(u_j = 1 \text{ for all events}\)                                         |
| 6     | 24    | \(N, Q \le 10^5\)                                                         |
| 7     | 11    | No additional constraints                                                  |

Starter code: