카테고리별 판매 집계

문제

온라인 쇼핑몰의 상품 카테고리는 1번 카테고리를 최상위로 하는 트리 구조이다. 1번을 제외한 각 카테고리 i는 상위 카테고리 p_i를 하나 가진다. 각 카테고리에는 오늘의 판매 점수 a_i가 있으며, 반품이 있으면 점수가 줄어들 수 있으므로 음수일 수도 있다. 운영 중에는 다음 세 종류의 작업이 순서대로 주어진다. 작업 1 v x: 카테고리 v의 판매 점수에 x를 더한다. 작업 2 v: 카테고리 v와 그 모든 하위 카테고리(v의 자손)의 판매 점수 합을 출력한다. 작업 3 v: 최상위 카테고리 1에서 카테고리 v까지의 경로에 있는 모든 카테고리(1과 v를 포함한다)의 판매 점수 합을 출력한다. 작업 1은 출력이 없고, 작업 2와 3은 해당 시점의 점수로 계산한 값을 출력한다. 모든 작업을 순서대로 처리하는 프로그램을 작성하시오. 출력해야 할 작업이 하나도 없는 경우는 입력에 주어지지 않는다.

입력

첫 줄에 카테고리 수 N과 작업 수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) N이 2 이상이면 둘째 줄에 p_2, ..., p_N이 공백으로 구분되어 주어진다. (1 ≤ p_i ≤ N, 주어진 간선은 1을 루트로 하는 트리를 이룬다. p_i < i라는 보장은 없다.) N이 1이면 이 줄은 생략된다. 다음 줄에 a_1, ..., a_N이 주어진다. (|a_i| ≤ 10^9) 이어서 Q개의 줄에 작업이 주어진다. 작업 1의 x는 |x| ≤ 10^9인 정수이고, v는 1 ≤ v ≤ N이다.

출력

작업 2와 작업 3마다 계산한 값을 입력 순서대로 한 줄에 하나씩 출력한다.

5 8
1 1 2 2
1 2 3 4 5
2 1
3 4
1 2 10
2 2
3 5
1 1 -4
3 3
2 1

15
7
21
18
0
21

1 3
-7
3 1
1 1 7
2 1

-7
0

출처: Devin.KR 자체 제작