| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 34 | 9 | 9 | 28.125% |
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_i$ and a learning level $l_i$. 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_i$. Sandu has success at market $i$ if his selling skill level is at least $t_i$ (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_j$ and $x_j$ meaning that on day $j,ドル there will be an event at the market $u_j$ and the learning level for the corresponding market will be permanently increased by $x_j$. In other words, event $j$ means that on day $j$ the learning level will be increased by $x_j$ ($l_{u_j} := l_{u_j} + x_j$).
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.
The first line of input contains two integers $N$ and $Q$ (1ドル ≤ N,Q ≤ 5 \cdot 10^5$).
The second line contains $N - 1$ integers that represent the rooted tree structure of the markets: $p_2 , \dots , p_N,ドル meaning that there exists an edge between $p_i$ and $i,ドル and $p_i$ is the parent of $i$.
Additionally for each $i,ドル the condition 1ドル ≤ p_i < i$ is always satisfied.
The third line contains $N$ integers: $t_1 , t_2 , \dots , t_N$ (0ドル ≤ t_i ≤ 10^9$) — 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_j$ and $x_j$ describing the event for $j$ th day (1ドル ≤ u_j ≤ N,ドル 1ドル ≤ x_j ≤ 10^9$).
Output $Q$ lines - in the $j$-th line you should output the answer for $j$-th day.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $p_i = 1$ for 1ドル < i ≤ N,ドル and $N,Q ≤ 2000$. |
| 2 | 8 | $N,Q ≤ 2000,ドル tree structure respects $p_i = i - 1$ for all $i$ |
| 3 | 17 | Tree structure respects $p_i = i - 1$ for 1ドル < i ≤ N$ |
| 4 | 12 | $N,Q ≤ 2000$ |
| 5 | 21 | $u_j = 1$ for all events |
| 6 | 24 | $N,Q ≤ 10^5$ |
| 7 | 11 | No additional constraints |
12 5 1 1 3 3 1 6 7 1 9 10 11 1 2 6 3 5 4 6 5 2 3 4 5 1 1 1 1 3 2 6 3 9 6
1 2 2 3 5
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.
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ドル$.
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ドル$.
After the third event, the answer doesn't change but the tree changes in the way shown below:
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$.
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ドル$.
5 4 1 2 3 4 1 2 5 6 7 1 1 1 2 1 1 1 2
1 2 2 4
5 5 1 1 1 1 1 2 3 4 5 4 4 2 2 5 5 1 1 3 3
1 1 1 2 2