P9168 [NOI Qualifier Joint Contest 2023] Personnel Scheduling

**Abusing the judging system for this problem will result in a ban.**

As is well known, the $n$ departments of a company can be organized into a tree structure. Formally, suppose these departments are numbered $1, \ldots, n$ in order. Then, except for department $1$, each department $i \in [2, n]$ has **exactly one** direct superior department $p_i \in [1, i - 1]$. In this way, the $n$ departments of the company can be viewed as a rooted tree with root $1$. If $i$ is a node in the subtree of $j$, then department $i$ is called a sub-department of department $j$. Initially, the company has $k$ outstanding employees, numbered $1 \ldots k$. The $i$-th outstanding employee initially works in department $x_i$ and has an ability value $v_i > 0$. To maximize the company's operational efficiency, the boss 0/\\/\G decides to make some personnel transfers. Specifically, the outstanding employee with number $i$ can be transferred to a sub-department of $x_i$, or not transferred (in which case the employee stays in department $x_i$). After that, the outstanding employees will compete to become the leader of their department—the one with the highest ability value will take the position and bring a contribution equal to their ability value to the company. If a department has no outstanding employees at all, then no leader can be chosen, and its contribution will be $0$. The company's performance is defined as the sum of contributions of all departments. Naturally, the boss 0/\\/\G wants to know how to transfer employees to maximize the company's performance. This is not difficult for him. However, the number of outstanding employees may also change. Specifically, there will be $m$ events in order, each of one of the following forms: - `1 x v`: First set $k = k + 1$, then add a new outstanding employee numbered $k$, whose initial department is $x$ and ability value is $v$. - `2 id`: The outstanding employee numbered $\mathit{id}$ will be fired. The boss 0/\\/\G wants you to tell him, at the beginning and after each event, what the maximum possible company performance is. Note that each round of personnel transfers is independent. That is, each time you compute the maximum possible performance, every outstanding employee returns to their own initial department.

The first line contains a positive integer $\mathit{sid}$, indicating the constraints and special properties for this test point. See the table below for details. The second line contains three integers $n, k, m$, representing the number of departments, the initial number of outstanding employees, and the number of events. The third line contains $n - 1$ positive integers $p_2, \ldots, p_n$, representing the direct superior department of each department. The next $k$ lines each contain two positive integers $x_i, v_i$, representing the initial department and ability value of an outstanding employee. The next $m$ lines each describe an event in the form `1 x v` or `2 id`.

Output one line containing $m + 1$ non-negative integers separated by single spaces, representing the maximum possible company performance at the beginning and after each event, in order.

**【Constraints】** For all testdata, it is guaranteed that: $1 \le \mathit{sid} \le 15$, $1 \le n, k \le 10^5$, $0 \le m \le 10^5$, $1 \le p_i < i$, $1 \le x_i, x \le n$, $1 \le v_i, v \le 10^5$. For event type 2, it is guaranteed that: $1 \le \mathit{id} \le k$, and the employee with number $\mathit{id}$ is still employed when this event happens. |Test Point ID|$\mathit{sid}$|$n \le$|$k \le$|$m \le$|Special Properties| |:-:|:-:|:-:|:-:|:-:|:-:| |1|$1$|$6$|$6$|$6$|None| |2, 3|$2$|$9$|$6$|$6$|None| |4, 5|$3$|$16$|$66$|$66$|None| |6 ~ 8|$4$|$66$|$66$|$0$|None| |9 ~ 11|$5$|$2,333$|$2,333$|$0$|None| |12 ~ 14|$6$|$10^5$|$10^5$|$0$|B| |15 ~ 18|$7$|$10^5$|$10^5$|$0$|None| |19 ~ 21|$8$|$2,333$|$2,333$|$2,333$|A| |22 ~ 24|$9$|$10^5$|$10^5$|$10^5$|AB| |25 ~ 28|$10$|$10^5$|$10^5$|$10^5$|A| |29 ~ 31|$11$|$2,333$|$2,333$|$2,333$|None| |32 ~ 34|$12$|$10^5$|$10^5$|$10^5$|C| |35 ~ 38|$13$|$10^5$|$10^5$|$10^5$|B| |39 ~ 44|$14$|$66,666$|$66,666$|$66,666$|None| |45 ~ 50|$15$|$10^5$|$10^5$|$10^5$|None| Special Property A: There are no events of type 2. Special Property B: $p_i = i - 1$. Special Property C: $v_i = v = 1$. Translated by ChatGPT 5