P7746 [COCI 2011/2012 #3] PLAĆE

Mirko likes cars, and he has finally managed to open his own car factory.

The factory has $n$ employees. Each employee has a boss (except that Mirko is considered the boss of everyone by default). Mirko is labeled as employee $1$, and the other employees are labeled $2 \sim n$. Each employee can increase or decrease the salaries of all of their subordinates (including direct subordinates and all subordinates in the hierarchy tree). Mirko’s duty is to prevent abuse of this power, so from time to time he wants to know the salary of some employee. He asks you to write a program that, given a sequence of commands (see the Input Format section), helps him monitor salary changes. Note: At any time, all salaries are positive integers and fit in a standard 32-bit integer type (`int` in C/C++, `longint` in Pascal).

The input has a total of $n + m + 1$ lines. The first line contains two integers $n, m$, representing the total number of employees and the number of commands. Lines $2 \sim n + 1$: on line $i$, two integers are given, representing the initial salary of employee $i - 1$ and their direct boss (note that Mirko has no boss, so on the line containing his information, only his initial salary is given). Lines $n + 2 \sim n + m + 1$: each line first contains a character indicating the command type, followed by the input described below: - If the character is `p`, then two integers $a, x$ follow, meaning that employee $a$ increases the salaries of all of their subordinates (including **direct subordinates** and **all subordinates they can indirectly control**) by $x$ (if $x$ is negative, it means decreasing salaries). - If the character is `u`, then only one integer $a$ follows, meaning that Mirko wants to know the salary of employee $a$.

For each `u` operation, output one line with one integer, representing the salary of the queried employee.

**Constraints** For all testdata, $1 \leqslant n, m \leqslant 5 \times 10^5$, $1 \leqslant a \leqslant n$, $-10^4 \leqslant x \leqslant 10^4$. **Source** This problem is from **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T5 PLAĆE_**, and with the original testdata configuration, the full score is $140$ points. Translated and organized by [Eason_AC](/user/112917), with minor adjustments by [123asdf123](/user/576074). Translated by ChatGPT 5