시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 4880 | 1387 | 933 | 30.460% |
상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다.
모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 모니터링 하려고 한다.
월급의 변화를 모니터링하는 프로그램을 작성하시오.
모든 직원의 월급은 항상 양의 정수이고 231-1 이하이다.
첫째 줄에 직원의 수 N과 월급 변화와 조사 쿼리의 수 M이 주어진다. (1 ≤ N, M ≤ 500,000)
다음 N개 줄의 i번째 줄에는 직원 i의 초기 월급과 상사의 번호가 주어진다. (상근이는 상사가 없기 때문에, 초기 월급만 주어진다)
다음 M개 줄에는 월급 변화와 조사 쿼리가 주어진다.
입력으로 u가 주어질 때마다 해당하는 직원의 월급을 출력한다.
2 3 5 3 1 p 1 5 u 2 u 1
8 5
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
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