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

Mirko 喜欢汽车，他终于成功地开办了自己的汽车工厂。

工厂有 $n$ 个员工，每个人都有一个上司（除了 Mirko 默认为每个人的上司）。Mirko 用 $1$ 号表示，其余员工用 $2\sim n$ 号表示。每个员工都可以提高或降低他所有下属（包括直接下属和等级树上的下属）的工资。Mirko 的职责是防止这种权力的滥用，所以他不时地想知道某个雇员的工资。他要求你写一个程序，给定一系列命令（见输入格式部分），帮助他监控工资的变化。注意：在任何时候，所有的工资都是正整数，并适合于标准的 $32$ 位整数类型（C/C++ 中的 `int`，Pascal 中的 `longint`）。

输入共 $n+m+1$ 行。 第一行，两个整数 $n,m$，分别表示员工的总数和指令的个数。 第 $2\sim n+1$ 行，第 $i$ 行两个整数分别表示第 $i-1$ 号员工的初始工资和他的直属上司（注意，Mirko 并没有上司，因此输入他的信息的那一行仅输入他的初始工资）。 第 $n+2\sim n+m+1$ 行，每行先输入一个字符表示命令类型，接下来的输入如下所述： - 如果字符为 `p`，接下来两个整数 $a,x$，表示员工 $a$ 将它的所有下属（包括**直系下属**和**他能够间接控制到的所有下属**）的工资增加了 $x$（如果 $x$ 是负数则相当于减少工资）。 - 如果字符为 `u`，接下来仅一个整数 $a$，表示 Mirko 想知道员工 $a$ 的工资。

对于每一个 `u` 操作，输出一行一个整数，表示被询问的员工的工资。

**【数据范围】** 对于所有数据，$1\leqslant n,m\leqslant 5\times 10^5$，$1\leqslant a\leqslant n$，$-10^4\leqslant x\leqslant 10^4$。 **【题目来源】** 本题来源自 **_[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_**，按照原题数据配置，满分 $140$ 分。 由 [Eason_AC](/user/112917) 翻译整理提供， [123asdf123](/user/576074) 微调。