회사 문화 3

시간 제한2초메모리 제한512 MB

요약

직원들이 루트 트리를 이룬다. 부하가 직원 i에게 준 칭찬 w는 i와 대통령까지의 모든 조상에 더해지고, 2번 질의는 그 직원이 받은 누적 칭찬을 묻는다.

난이도: 보통10점 중 5점
유형: 트리, DFS, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

영선회사에는 상사가 직속 부하를 칭찬하면 그 부하 밑에 있는 모든 직원에게 칭찬이 연쇄적으로 내려가는 문화가 있다. 사장 영선이는 이 방향을 딱 하루만 뒤집기로 했다. 부하가 상사를 칭찬하면, 그 상사부터 사장까지 위로 이어지는 모든 직원이 같은 크기의 칭찬을 받는다.

칭찬 정보는 실시간으로 들어온다. 쿼리는 두 종류다.

1 i w: i번 직원이 직속 부하 한 명에게서 $w$ 만큼 칭찬을 받는다. 이 $w$ 는 i번 직원과 i번의 모든 상사에게 각각 더해진다. ( $1 \le i \le n$ , $1 \le w \le 1000$ ) 직속 부하가 없는 직원은 이 쿼리로 주어지지 않는다.
2 i: i번 직원이 지금까지 받은 칭찬의 총합을 출력한다. ( $1 \le i \le n$ )

입력

첫째 줄에 직원 수 $n$ 과 쿼리 수 $m$ 이 주어진다. 직원에게는 1번부터 $n$ 번까지 번호가 매겨져 있다. ( $2 \le n, m \le 100\,000$ )

둘째 줄에 1번부터 $n$ 번까지 각 직원의 직속 상사 번호가 순서대로 주어진다. 직속 상사의 번호는 항상 자기 번호보다 작다. 1번이 사장이고 상사가 없으므로, 1번 자리에는 -1이 주어진다.

다음 $m$ 개 줄에 쿼리가 한 줄에 하나씩 주어진다.

출력

2번 쿼리가 주어질 때마다, 그 직원이 받은 칭찬의 총합을 한 줄에 하나씩 출력한다.

예제7

예제 1

입력

예상 출력

0
10
12

예제 2
입력
```
2 3
-1 1
1 1 1000
2 1
2 2
```
예상 출력
```
1000
0
```

예제 3

입력

6 8
-1 1 1 1 1 1
2 1
1 1 7
2 1
2 4
1 1 993
2 1
2 6
2 2

예상 출력

예제 4

입력

6 12
-1 1 1 2 2 3
2 1
1 2 5
2 1
2 2
2 3
1 3 7
2 1
2 3
1 1 3
2 1
2 2
2 4

예상 출력

예제 5
입력
```
4 4
-1 1 2 2
2 1
2 2
2 3
2 4
```
예상 출력
```
0
0
0
0
```

예제 6

입력

예상 출력

예제 7

입력

15 20
-1 1 1 2 2 3 3 4 4 5 5 6 6 7 7
1 4 10
1 5 20
1 6 30
1 7 40
1 2 1
1 3 2
1 1 100
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13

예상 출력