시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB4880138793330.460%

문제

상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다.

모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 모니터링 하려고 한다.

월급의 변화를 모니터링하는 프로그램을 작성하시오.

모든 직원의 월급은 항상 양의 정수이고 231-1 이하이다.

입력

첫째 줄에 직원의 수 N과 월급 변화와 조사 쿼리의 수 M이 주어진다. (1 ≤ N, M ≤ 500,000)

다음 N개 줄의 i번째 줄에는 직원 i의 초기 월급과 상사의 번호가 주어진다. (상근이는 상사가 없기 때문에, 초기 월급만 주어진다)

다음 M개 줄에는 월급 변화와 조사 쿼리가 주어진다.

  1. p a x가 주어진 경우 a의 모든 부하의 월급을 x만큼 증가시킨다. (-10,000 ≤ x ≤ 10,000)
  2. u a가 주어진 경우에는 a의 월급을 출력한다.

출력

입력으로 u가 주어질 때마다 해당하는 직원의 월급을 출력한다.

예제 입력 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
W3sicHJvYmxlbV9pZCI6IjI4MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWIzZDlcdWNjMjggXHVhY2Y1XHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4XHViOTdjIFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1Yzc5MFx1YjNkOVx1Y2MyOCBcdWFjZjVcdWM3YTVcdWM1ZDAgXHVjZGU4XHVjOWMxXHVkNTVjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjYzRcdWMxOGRcdWI0MWMgXHVjMmI5XHVjOWM0IFx1YjA1ZFx1YzVkMCBcdWI0ZGNcdWI1MTRcdWM1YjQgXHVjMGFjXHVjN2E1XHVjNzc0IFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVhY2Y1XHVjN2E1XHVjNWQwXHViMjk0IFx1Y2QxZCBOXHViYTg1XHVjNzU4IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzljMVx1YzZkMFx1Yzc0MCBcdWQ1NWMgXHViYTg1XHVjNzU4IFx1YzBjMVx1YzBhY1x1YWMwMCBcdWM3ODhcdWIyZTQuIChcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMwYzFcdWMwYWNcdWM3NzRcdWIyZTQpIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1YzljMVx1YzZkMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMlx1YmQ4MFx1ZDEzMCBOXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZDgwXHVkNTU4IFx1YzljMVx1YzZkMChcdWM5YzFcdWMxOGQgXHViZDgwXHVkNTU4XHVjNjQwIFx1YmQ4MFx1ZDU1OFx1Yzc1OCBcdWJkODBcdWQ1NThcdWI0ZjFcdWI0ZjFcdWM3NDQgXHViYWE4XHViNDUwIFx1ZDNlY1x1ZDU2OClcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzQ0IFx1Yzc3OFx1YzBjMVx1ZDU1OFx1YWM3MFx1YjA5OCBcdWMwYWRcdWFjMTBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWQ4Y1x1YjgyNSBcdWIwYThcdWM2YTlcdWM3NDQgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM5YzFcdWM2ZDBcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzQ0IFx1YmFhOFx1YjJjOFx1ZDEzMFx1YjljMSBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDRcdWFlMDlcdWM3NTggXHViY2MwXHVkNjU0XHViOTdjIFx1YmFhOFx1YjJjOFx1ZDEzMFx1YjljMVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzU4IFx1YzZkNFx1YWUwOVx1Yzc0MCBcdWQ1NmRcdWMwYzEmbmJzcDtcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwIDI8c3VwPjMxPFwvc3VwPi0xIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjNmQwXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzZkNFx1YWUwOSBcdWJjYzBcdWQ2NTRcdWM2NDAgXHVjODcwXHVjMGFjIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgTSAmbGU7IDUwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzFcdWM2ZDAgaVx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjNmQ0XHVhZTA5XHVhY2ZjIFx1YzBjMVx1YzBhY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBjMVx1YzBhY1x1YWMwMCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWNkMDhcdWFlMzAgXHVjNmQ0XHVhZTA5XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzZkNFx1YWUwOSBcdWJjYzBcdWQ2NTRcdWM2NDAgXHVjODcwXHVjMGFjIFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+cCBhIHhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWNiZFx1YzZiMCBhXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJkODBcdWQ1NThcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzQ0IHhcdWI5Y2NcdWQwN2MgXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGE4XHViMmU0LiAoLTEwLDAwMCAmbGU7IHggJmxlOyAxMCwwMDApPFwvbGk+XHJcblx0PGxpPnUgYVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IGFcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyB1XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzljMVx1YzZkMFx1Yzc1OCBcdWM2ZDRcdWFlMDlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQTEFcdTAxMDZFIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBsb3ZlcyBjYXJzIGFuZCBoZSBmaW5hbGx5IG1hbmFnZWQgdG8gc3RhcnQgaGlzIG93biBjYXIgZmFjdG9yeSEgRmFjdG9yeSBoYXMgTiBlbXBsb3llZXMsIGVhY2ggb2YgdGhlbSBoYXMgZXhhY3RseSBvbmUgc3VwZXJpb3IgKGV4Y2VwdCBNaXJrbyAtIGhlIGlzIGJ5IGRlZmF1bHQgZXZlcnlib2R5JnJzcXVvO3Mgc3VwZXJpb3IpLiBNaXJrbyBpcyBkZW5vdGVkIGJ5IG51bWJlciAxLCBhbmQgdGhlIHJlc3Qgb2YgdGhlIGVtcGxveWVlcyB3aXRoIG51bWJlcnMgMiB0byBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FdmVyeSBlbXBsb3llZSBjYW4gcmFpc2Ugb3IgbG93ZXIgdGhlIHdhZ2VzIG9mIGFsbCBvZiBoaXMgc3Vib3JkaW5hdGVzIChib3RoIGRpcmVjdCBzdWJvcmRpbmF0ZXMgYW5kIHRob3NlIGxvd2VyIGluIHRoZSBoaWVhcmFyY2h5IHRyZWUpLiBNaXJrbyZyc3F1bztzIHJvbGUgaXMgdG8gcHJldmVudCBhYnVzZSBvZiBzdWNoIHBvd2VyLCBzbyBmcm9tIHRpbWUgdG8gdGltZSBoZSB3YW50cyB0byBrbm93IHdhZ2Ugb2YgYSBwYXJ0aWN1bGFyIGVtcGxveWVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZSBpcyBhc2tpbmcgeW91IHRvIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCB3aWxsIGhlbHAgaGltIG1vbml0b3Igd2FnZSBjaGFuZ2VzLCBnaXZlbiBhIHNlcXVlbmNlIG9mIGNvbW1hbmRzIGRlc2NyaWJlZCBpbiB0aGUgaW5wdXQgc2VjdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UmVtYXJrOiBhdCBhbnkgdGltZSwgYWxsIG9mIHRoZSB3YWdlcyB3aWxsIGJlIHBvc2l0aXZlIGludGVnZXJzIGFuZCB3aWxsIGZpdCBpbiBzdGFuZGFyZCAzMi1iaXQgaW50ZWdlciB0eXBlIChpbnQgaW4gQ1wvQysrLCBsb25naW50IGluIFBhc2NhbCkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMgTiAoMSAmbGU7IE4gJmxlOyA1MDAgMDAwKSwgbnVtYmVyIG9mIGVtcGxveWVlcywgYW5kIE0gKDEgJmxlOyBNICZsZTsgNTAwIDAwMCksIG51bWJlciBvZiB3YWdlIGNoYW5nZXMgYW5kIHdhZ2UgcXVlcmllcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TmV4dCBOIGxpbmVzIGNvbnRhaW4gdGhlIGluZm9ybWF0aW9uIGFib3V0IGVtcGxveWVlcyAxLCAyLCAuLi4sIE4gKHJlc3BlY3RpdmVseSk6IHN0YXJ0aW5nIHdhZ2UgYW5kIHRoZSBpZGVudGlmaWVyIG9mIGhpcyBkaXJlY3Qgc3VwZXJ2aXNvci4gUmVtYXJrOiBNaXJrbyBoYXMgbm8gc3VwZXJ2aXNvciwgc28gaGlzIGxpbmUgd2lsbCBjb250YWluIG9ubHkgaGlzIHN0YXJ0aW5nIHdhZ2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5leHQgTSBsaW5lcyBjb250YWluIG9uZSBvZiB0aGUgZm9sbG93aW5nOiZuYnNwOzxcL3A+XHJcblxyXG48cD5wIEEgWCAtIGVtcGxveWVlIEEgaW5jcmVhc2VzIChvciBkZWNyZWFzZXMgaW4gY2FzZSBvZiBhIG5lZ2F0aXZlIFgpIHdhZ2Ugb2YgYWxsIGhpcyBzdWJvcmRpbmF0ZXMgYnkgdGhlIGFtb3VudCBYICgtMTAgMDAwICZsZTsgWCAmbGU7IDEwIDAwMCk7Jm5ic3A7PGJyIFwvPlxyXG51IEEgLSBNaXJrbyB3YW50cyB0byBrbm93IHRoZSB3YWdlIG9mIGVtcGxveWVlIEEuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBsaW5lIGZvciBlYWNoICZsc3F1bzsyJnJzcXVvOyBxdWVyeSBpbiB0aGUgaW5wdXQgLSB0aGUgY3VycmVudCB3YWdlIG9mIHRoZSBnaXZlbiBlbXBsb3llZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #3 5번

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: rdd6584
  • 문제의 오타를 찾은 사람: sohnryang