Company Performance Maximization

A company has n departments organized as a tree with department 1 as the root. For each department i (2 ≤ i ≤ n), there is exactly one superior department p_i with 1 ≤ p_i < i. In other words, the departments form a tree rooted at 1. If department i is in the subtree of department j, then i is called a sub-department of j.

Initially, the company has k excellent employees, numbered from 1 to k. The i-th employee works in department x_i and has a positive ability value v_i. To maximize the company’s performance, the boss can reassign each employee to any department in the subtree of his/her initial department (including the original department) or leave him/her in place. After the reassignments, every department conducts an election for a leader. The leader is the excellent employee with the highest ability value in that department, and the contribution of the department is equal to the ability value of its leader. If a department has no excellent employees, its contribution is 0. The company’s overall performance is defined as the sum of contributions of all departments.

Furthermore, there will be m events. Each event is one of the following types:

• 1 x v: A new excellent employee is added. Let the new employee have number k+1, work initially in department x, and have ability v (update k to k+1).
• 2 id: The employee with number id is dismissed.

After each event – as well as in the initial state – the boss wants to know the maximum possible overall performance of the company, assuming that the reassignments are chosen optimally. Note that each performance computation is independent – every excellent employee starts from his/her original department for that computation.

Hint: By doing an Euler tour on the department tree, each department can be mapped to an index. For an employee in department x, the set of departments he/she can be reassigned to corresponds to the interval [tin(x), tout(x)] in the Euler order. The problem then reduces to selecting a set of employees and assigning each one a unique department from his/her interval such that the sum of their ability values is maximized.

Mathematically, if an employee i initially works in department x_i, let his/her available interval be \(\left[ tin(x_i),\, tout(x_i) \right]\). We wish to select a subset of employees and assign to each a unique department j within his/her interval, so that the total sum \(\sum v_i\) is maximized.

inputFormat

The first line contains one integer n (the number of departments).

The second line contains n - 1 integers: p₂, p₃, …, p_n, where p_i denotes the direct superior department of department i (1 ≤ p_i < i).

The next line contains one integer k (the initial number of excellent employees).

Each of the following k lines contains two integers x and v, representing that an excellent employee works initially in department x with ability value v (v > 0).

The next line contains one integer m (the number of events).

Each of the following m lines represents an event in one of the two formats:

• 1 x v
• 2 id

It is guaranteed that when an employee is dismissed, he/she is currently employed. The employees are numbered in the order of their addition (initial employees are numbered 1 through k).

outputFormat

Output m + 1 lines. The first line should be the maximum possible overall company performance computed from the initial set of excellent employees. Then, after each event, output a line containing the maximum possible overall performance after processing that event.

sample

3
1 1
2
1 100
2 50
2
1 2 60
2 1

150
160
60

</p>