문제
N명이 근무하는 회사가 있다. 이 회사의 사원은 1 이상 N 이하의 서로 다른 번호를 갖고 있다.
번호가 1인 사원은 회사의 사장이고, 번호가 2 이상인 사원은 한 명의 상사가 있다. 모든 사원은 자신이 사장이거나, 자신의 상사가 사장이거나, 자신의 상사의 상사가 사장이거나, ... 를 만족한다.
이 회사에서 특정 사원 A의 부하 직원은 다음과 같이 정한다.
직원 B의 상사가 A라면 B는 A의 부하 직원이다.
직원 B의 상사의 상사가 A라면 B는 A의 부하 직원이다.
직원 B의 상사의 ...의 상사가 A라면 B는 A의 부하 직원이다.
위 조건을 만족하지 않는 직원들은 A의 부하 직원이 아니다.
우리는 회사 직원들의 연봉을 계산하는 전산 시스템을 개발해야 한다. 시스템은 아래 두 가지 기능을 빠르게 처리해야 한다.
특정 직원의 부하 직원들의 연봉을 일괄적으로 X만큼 더한다. X가 음수라면 직원들의 연봉이 깎인다.
특정 직원의 연봉을 계산한다.
사원의 초기 연봉은 1 이상 231-1 이하이며, 연봉이 바뀌더라도 해당 범위를 벗어나지 않는다.
입력
첫째 줄에 사원의 수 N (1 ≤ N ≤ 500,000)와 질문의 수 Q (1 ≤ Q ≤ 500,000)가 주어진다.
둘째 줄에 1번 사원의 연봉이 주어진다.
셋째 줄부터 N-1개의 줄에는 2, ..., N번 사원의 연봉과 상사 번호가 공백을 사이에 두고 주어진다.
다음 Q개의 줄에는 질문의 정보가 아래 두 방식 중 한 가지로 주어진다.
p i X: i번 사원의 부하 직원들의 연봉이 X만큼 늘거나 줄어든다. (-10,000 ≤ X ≤ 10,000)u i: i번 사원의 연봉을 구해라.
u i 방식 질문은 적어도 한 번 등장한다.
출력
모든 u i 방식 질문에 대하여 한 줄에 하나씩 연봉을 출력한다.
예제 #1
2 3
5
3 1
p 1 5
u 2
u 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
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
7
9
7
5
로그인해야 코드를 작성할 수 있어요.