2049: 建树+先序遍历

尔科热爱汽车，他终于开了自己的汽车工厂！工厂有$N$名员工，每个人都有一名上级（除了米尔科——他默认是每个人的上级）。米尔科用数字$1$表示，其余员工用数字$2$到$N$表示。

每个员工都可以提高或降低其所有下属（包括直接下属和层级树中较低的下属）的工资。米尔科的作用是防止滥用这种权力，所以他不时想知道某个特定员工的工资。他要求你编写一个程序，根据输入部分描述的一系列命令，帮助他监控工资变化。

备注：任何时候，所有工资都将是正整数，并符合标准$32$位整数类型（$C/C++$中的$int，Pascal$中的$longint$）。

输入格式:

输入的第一行包含两个空格分隔的正整数$N（1\le N\le 500000）$，表示员工人数，$（1\le M\le 500000）$，表示工资变动和工资查询的数量。

接下来的$N$行包含关于员工$1、2、。。。，N$（分别）：表示起始工资和其直接主管的标识符。

备注：米尔科没有主管，所以他的行只包含他的起始工资。

接下来的$M$行包含以下内容之一：

$1.pAX$——员工$A$将其所有下属的工资增加（或在负$X$表示减少）$X（-10000\le X\le 10000);$
$2.uA-Mirko$想知道员工$A$的工资。

输出格式:

对于输入中的每个“$2$”查询，输出应该包含一行——给定员工的当前工资。

输入样例1:

2 3
5
3 1
p 1 5
u 2
u 1

输出样例1:

8
5

输入样例2:

5 5
4
2 1
6 1
7 1
3 4
u 3
p 1 -1
u 3
p 4 5
u 5

输出样例2:

6
5
7

输入样例3:

6 7
5
4 1
3 2
7 3
2 3
3 5
p 3 2
p 2 4
u 3
u 6
p 5 -2
u 6
u 1

输出样例3:

7
9
7
5

The first line of the input is a positive integer n which is the number of puzzles that follow. Each puzzle will be five lines, each of which has six 0's or 1's separated by one or more spaces. A 0 indicates that the light is off, while a 1 indicates that the light is on initially.

For each puzzle, the output consists of a line with the string: "PUZZLE #m", where m is the index of the puzzle in the input file. Following that line, is a puzzle-like display (in the same format as the input) . In this case, 1's indicate buttons that must be pressed to solve the puzzle, while 0's indicate buttons, which are not pressed. There should be exactly one space between each 0 or 1 in the output puzzle-like display.