New Year's '17 P7 - Santa's Deliveries - Olympiads Online Judge

New Year's '17 P7 - Santa's Deliveries

Points: 25 (partial)

Time limit: 2.5s

Memory limit: 256M

Author:

Problem types

Santa has gone around the world and delivered to every country around the world on Christmas, except one: North Korea. Unsurprisingly, all the kids in North Korea have been naughty this year; except for Kim Jong Un and his $N-1$ $N - 1$ guards in his triangular hotel in Pyongyang.

Each of the $N$ $N$ rooms (labeled $1 \dots N$ $1 \dots N$ ) in Kim's hotel has a fireplace for Santa to drop off presents. Each fireplace is either connected to the chimney or to exactly $1$ $1$ fireplace above it via a pipe. Each pipe may take a different amount of time for Santa to cross.

Being the ~~naughty kid~~ genius leader he is, Kim is trying to capture Santa to ~~steal all the toys~~ distribute the wealth. Kim set up a grapple gun pointing up in each of the fireplaces, waiting to grab Santa as soon as he enters the chimney. The grapple gun's projectile will travel along the pipes until it reaches the chimney. Unfortunately, the Soviet era detection systems and wiring are quite out of date and thus take time to give the signal to each of the grapple guns. Specifically, the grapple gun at the $i^{th}$ $i^{t h}$ fireplace will fire $D_i$ $D_{i}$ seconds after Santa has entered the chimney.

Thankfully, Kim has all his best technicians working on a solution now. Before Santa arrives, Kim's technicians will make $C$ $C$ changes in the system that changes the delay of the grapple gun at the $u^{th}$ $u^{t h}$ fireplace to $v$ $v$ seconds. Because of their outdated training, they might even make the problem worse by increasing the delay time.

Santa wants to find a path down that will allow him to deliver the greatest number of presents without getting caught with a grapple gun. Santa will instantly fly out of the hotel the moment a grapple gun at or below him fires. Help him find save Christmas by calculating the value after each change Kim's technicians make.

Note: It takes Santa zero time to deliver the presents. However, if Santa arrives at a fireplace just as the grapple gun fires, he will not be able to deliver the present.

Input Specification

The first line contains $N$ $N$ , the number of nodes ( $1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$ ).

Followed by $N$ $N$ space separated integers indicating the delays on the grapple guns initially. The delays will always be a positive integer less than or equal to $10^9$ $10^{9}$ .

Followed by $N$ $N$ lines containing a pair of integers, the (parent, time to cross in seconds). Having 0 for parent means it's connected to the chimney. The time to cross will be a positive integer no greater than $10^9$ $10^{9}$ .

The next line contains $C$ $C$ , the number of changes ( $1 \le C \le 10^5$ $1 \leq C \leq 10^{5}$ ).

Followed by $C$ $C$ lines containing a pair of integers, the fireplace changed (1 indexed, chimney does not have a grapple gun and will never be changed) and the new time.

Output Specification

After each change, print the answer on its own line.

Subtask	Marks	Additional Constraints
1	10%	$N \le 5, C \le 5$ $N \leq 5, C \leq 5$
2	15%	$N \le 100$ $N \leq 100$ , each grapple gun will receive at most $1$ $1$ fix.
3	15%	$N \le 1\,000$ $N \leq 1 000$ , the delay on each grapple gun will never increase.
4	20%	The parent of the $i^{th}$ $i^{t h}$ fireplace will be $i-1$ $i - 1$ .
5	40%	No additional constraints.

Sample Input

Copy

5
10 2 10 2 10
0 1
1 2
2 4
1 1
2 6
4
4 5
4 1
2 10
4 10

Sample Output

Copy

Sample Explanation

Before any changes, the most Santa could deliver is 1 present. After he delivers a present to fireplace #1, there wouldn't be enough time to deliver to any others. If he tried going to #4, he would get hooked in by the grapple gun as he arrives.

The first change opens a path for Santa to deliver to #4, allowing him to deliver 2 presents.

The second change makes the grapple gun at #4 fire very early, thus Santa could not even deliver a single present safely.

The third change delays the firing of #2 significantly, but Santa isn't even able to get to #1 before the grapple gun at #4 fires, so he still can't deliver any presents.

The fourth change delays the firing of #4 significantly, allowing Santa to go all the way to either #3 or #5 to deliver 3 presents.

Comments

0

WillFlame commented on Jan. 1, 2017, 11:43 p.m.

Do the grapple gun projectiles take the same amount of time that Santa does to go through each pipe or do they travel instantly?

0

r3mark commented on Jan. 1, 2017, 11:46 p.m.

They travel instantly.

0

WillFlame commented on Jan. 1, 2017, 11:49 p.m.

Then does it matter if a grapple gun fires at a fireplace that Santa has already visited?

0

r3mark commented on Jan. 2, 2017, 12:06 a.m.

If a grapple gun fires which affects fireplace i after Santa visits fireplace i, then nothing happens.

1

rameshaggarwal commented on Jan. 1, 2017, 11:59 p.m.

The statement is so confusing. I got 120 points assuming and guessing everything. The main point is(and they should bold it): Santa always goes down(there is no path just a line).

-1

kobortor commented on Jan. 2, 2017, 5:14 a.m.

Um thats what a path is.

0
rameshaggarwal commented on Jan. 1, 2017, 11:07 p.m.
I can't understand various points in question:

Why is Santa not able to deliver to 1 in 2nd change(4 1)? Does grapple gun's projectile travel at infinite speed?

If projectile always travels upwards, can Santa delay his time in a path favorably to reach other nodes?

Can more than one node have 0 as parent?

0
r3mark commented on Jan. 2, 2017, 12:11 a.m.
Sorry about the delay.

Yes, the grappling gun instantly affects all fireplaces in the path from fireplace 0 to whatever fireplace the gun is at.

Santa cannot wait for the grappling gun to simply pass by a fireplace which he wants to go to. Once a grappling gun reaches a fireplace, Santa can never go to that fireplace (within that query of course).

Yes.

0

alei commented on Jan. 1, 2017, 5:10 p.m.

.

0

kobortor commented on Jan. 1, 2017, 5:21 p.m.

Delays are limited at $10^9$ $10^{9}$