시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1154 247 154 34.685%

문제

상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 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

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

예제 출력 1

7
9
7
5
W3sicHJvYmxlbV9pZCI6IjI4MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWIzZDlcdWNjMjggXHVhY2Y1XHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4XHViOTdjIFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1Yzc5MFx1YjNkOVx1Y2MyOCBcdWFjZjVcdWM3YTVcdWM1ZDAgXHVjZGU4XHVjOWMxXHVkNTVjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjYzRcdWMxOGRcdWI0MWMgXHVjMmI5XHVjOWM0IFx1YjA1ZFx1YzVkMCBcdWI0ZGNcdWI1MTRcdWM1YjQgXHVjMGFjXHVjN2E1XHVjNzc0IFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVhY2Y1XHVjN2E1XHVjNWQwXHViMjk0IFx1Y2QxZCBOXHViYTg1XHVjNzU4IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzljMVx1YzZkMFx1Yzc0MCBcdWQ1NWMgXHViYTg1XHVjNzU4IFx1YzBjMVx1YzBhY1x1YWMwMCBcdWM3ODhcdWIyZTQuIChcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMwYzFcdWMwYWNcdWM3NzRcdWIyZTQpIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1YzljMVx1YzZkMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMlx1YmQ4MFx1ZDEzMCBOXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZDgwXHVkNTU4IFx1YzljMVx1YzZkMChcdWM5YzFcdWMxOGQgXHViZDgwXHVkNTU4XHVjNjQwIFx1YmQ4MFx1ZDU1OFx1Yzc1OCBcdWJkODBcdWQ1NThcdWI0ZjFcdWI0ZjFcdWM3NDQgXHViYWE4XHViNDUwIFx1ZDNlY1x1ZDU2OClcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzQ0IFx1Yzc3OFx1YzBjMVx1ZDU1OFx1YWM3MFx1YjA5OCBcdWMwYWRcdWFjMTBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWQ4Y1x1YjgyNSBcdWIwYThcdWM2YTlcdWM3NDQgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM5YzFcdWM2ZDBcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzQ0IFx1YmFhOFx1YjJjOFx1ZDEzMFx1YjljMSBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDRcdWFlMDlcdWM3NTggXHViY2MwXHVkNjU0XHViOTdjIFx1YmFhOFx1YjJjOFx1ZDEzMFx1YjljMVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzU4IFx1YzZkNFx1YWUwOVx1Yzc0MCBcdWQ1NmRcdWMwYzEmbmJzcDtcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwIDI8c3VwPjMxPFwvc3VwPi0xIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjNmQwXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzZkNFx1YWUwOSBcdWJjYzBcdWQ2NTRcdWM2NDAgXHVjODcwXHVjMGFjIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgTSAmbGU7IDUwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzFcdWM2ZDAgaVx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjNmQ0XHVhZTA5XHVhY2ZjIFx1YzBjMVx1YzBhY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBjMVx1YzBhY1x1YWMwMCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWNkMDhcdWFlMzAgXHVjNmQ0XHVhZTA5XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzZkNFx1YWUwOSBcdWJjYzBcdWQ2NTRcdWM2NDAgXHVjODcwXHVjMGFjIFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEuIHAgYSB4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjYmRcdWM2YjAgQVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZDgwXHVkNTU4XHVjNzU4IFx1YzZkNFx1YWUwOVx1Yzc0NCBYXHViOWNjXHVkMDdjIFx1Yzk5ZFx1YWMwMFx1YzJkY1x1ZDBhOFx1YjJlNC4gKC0xMCwwMDAgJmxlOyBYICZsZTsgMTAsMDAwKTxcL3A+XHJcblxyXG48cD4yLiB1IGFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBBXHVjNzU4IFx1YzZkNFx1YWUwOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIHVcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0Y1x1YjljOFx1YjJlNCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjOWMxXHVjNmQwXHVjNzU4IFx1YzZkNFx1YWUwOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBMQVx1MDEwNkUiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGxvdmVzIGNhcnMgYW5kIGhlIGZpbmFsbHkgbWFuYWdlZCB0byBzdGFydCBoaXMgb3duIGNhciBmYWN0b3J5ISBGYWN0b3J5IGhhcyBOIGVtcGxveWVlcywgZWFjaCBvZiB0aGVtIGhhcyBleGFjdGx5IG9uZSBzdXBlcmlvciAoZXhjZXB0IE1pcmtvIC0gaGUgaXMgYnkgZGVmYXVsdCBldmVyeWJvZHkmcnNxdW87cyBzdXBlcmlvcikuIE1pcmtvIGlzIGRlbm90ZWQgYnkgbnVtYmVyIDEsIGFuZCB0aGUgcmVzdCBvZiB0aGUgZW1wbG95ZWVzIHdpdGggbnVtYmVycyAyIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IGVtcGxveWVlIGNhbiByYWlzZSBvciBsb3dlciB0aGUgd2FnZXMgb2YgYWxsIG9mIGhpcyBzdWJvcmRpbmF0ZXMgKGJvdGggZGlyZWN0IHN1Ym9yZGluYXRlcyBhbmQgdGhvc2UgbG93ZXIgaW4gdGhlIGhpZWFyYXJjaHkgdHJlZSkuIE1pcmtvJnJzcXVvO3Mgcm9sZSBpcyB0byBwcmV2ZW50IGFidXNlIG9mIHN1Y2ggcG93ZXIsIHNvIGZyb20gdGltZSB0byB0aW1lIGhlIHdhbnRzIHRvIGtub3cgd2FnZSBvZiBhIHBhcnRpY3VsYXIgZW1wbG95ZWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlIGlzIGFza2luZyB5b3UgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoIHdpbGwgaGVscCBoaW0gbW9uaXRvciB3YWdlIGNoYW5nZXMsIGdpdmVuIGEgc2VxdWVuY2Ugb2YgY29tbWFuZHMgZGVzY3JpYmVkIGluIHRoZSBpbnB1dCBzZWN0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SZW1hcms6IGF0IGFueSB0aW1lLCBhbGwgb2YgdGhlIHdhZ2VzIHdpbGwgYmUgcG9zaXRpdmUgaW50ZWdlcnMgYW5kIHdpbGwgZml0IGluIHN0YW5kYXJkIDMyLWJpdCBpbnRlZ2VyIHR5cGUgKGludCBpbiBDXC9DKyssIGxvbmdpbnQgaW4gUGFzY2FsKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycyBOICgxICZsZTsgTiAmbGU7IDUwMCAwMDApLCBudW1iZXIgb2YgZW1wbG95ZWVzLCBhbmQgTSAoMSAmbGU7IE0gJmxlOyA1MDAgMDAwKSwgbnVtYmVyIG9mIHdhZ2UgY2hhbmdlcyBhbmQgd2FnZSBxdWVyaWVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5OZXh0IE4gbGluZXMgY29udGFpbiB0aGUgaW5mb3JtYXRpb24gYWJvdXQgZW1wbG95ZWVzIDEsIDIsIC4uLiwgTiAocmVzcGVjdGl2ZWx5KTogc3RhcnRpbmcgd2FnZSBhbmQgdGhlIGlkZW50aWZpZXIgb2YgaGlzIGRpcmVjdCBzdXBlcnZpc29yLiBSZW1hcms6IE1pcmtvIGhhcyBubyBzdXBlcnZpc29yLCBzbyBoaXMgbGluZSB3aWxsIGNvbnRhaW4gb25seSBoaXMgc3RhcnRpbmcgd2FnZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TmV4dCBNIGxpbmVzIGNvbnRhaW4gb25lIG9mIHRoZSBmb2xsb3dpbmc6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPnAgQSBYIC0gZW1wbG95ZWUgQSBpbmNyZWFzZXMgKG9yIGRlY3JlYXNlcyBpbiBjYXNlIG9mIGEgbmVnYXRpdmUgWCkgd2FnZSBvZiBhbGwgaGlzIHN1Ym9yZGluYXRlcyBieSB0aGUgYW1vdW50IFggKC0xMCAwMDAgJmxlOyBYICZsZTsgMTAgMDAwKTsmbmJzcDs8YnIgXC8+XHJcbnUgQSAtIE1pcmtvIHdhbnRzIHRvIGtub3cgdGhlIHdhZ2Ugb2YgZW1wbG95ZWUgQS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIGxpbmUgZm9yIGVhY2ggJmxzcXVvOzImcnNxdW87IHF1ZXJ5IGluIHRoZSBpbnB1dCAtIHRoZSBjdXJyZW50IHdhZ2Ugb2YgdGhlIGdpdmVuIGVtcGxveWVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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