Plaće
Mirko obožava automobile te je konačno uspio otvoriti vlastitu tvornicu automobila. Tvornica ima N zaposlenika, a svaki od njih ima točno jednog izravno nadređenog zaposlenika, osim Mirka koji je nadređen svima. Mirko je označen brojem 1, a ostali zaposlenici brojevima od 2 do N.
Svaki zaposlenik može povisiti ili sniziti plaću svima sebi podređenima (bilo da su mu izravno ili neizravno podređeni). Mirko će, naravno, paziti da se to pravo ne zloupotrebljava te od vas traži da napišete program koji će simulirati promjene u plaćama. Zadane su vam početne plaće, kao i sve promjene i upiti redom kojim su se događali. Vaš program treba odgovarati na dane upite.
Napomena: plaće svih zaposlenika u svakom će trenutku biti pozitivne i stat će u standardni 32-bitni cjelobrojni tip podatka (int u C/C++, longint u Pascalu).
Svaki zaposlenik može povisiti ili sniziti plaću svima sebi podređenima (bilo da su mu izravno ili neizravno podređeni). Mirko će, naravno, paziti da se to pravo ne zloupotrebljava te od vas traži da napišete program koji će simulirati promjene u plaćama. Zadane su vam početne plaće, kao i sve promjene i upiti redom kojim su se događali. Vaš program treba odgovarati na dane upite.
Napomena: plaće svih zaposlenika u svakom će trenutku biti pozitivne i stat će u standardni 32-bitni cjelobrojni tip podatka (int u C/C++, longint u Pascalu).
Input U prvom retku ulaza nalaze se, odvojeni razmakom, prirodni brojevi N (1 ≤ N ≤ 500 000), broj radnika, i M (1 ≤ M ≤ 500 000), ukupan broj promjena i upita o plaćama.U sljedećih N redaka nalaze se podaci o radnicima: u svakom retku nalazi se početna plaća radnika (prirodan broj) te oznaka njemu izravno nadređenog radnika, osim kod Mirka kod koga je zadana samo
početna plaća jer on nema nadređenih.
U svakom od sljedećih M redaka nalazi se jedno od sljedećeg:
1. p A X - zaposlenik označen brojem A povećava (ili smanjuje ukoliko je X negativan) plaću svima sebi podređenima za iznos X (-10 000 ≤ X ≤ 10 000);
2. u A - Mirka zanima plaća zaposlenika označenog brojem A.
početna plaća jer on nema nadređenih.
U svakom od sljedećih M redaka nalazi se jedno od sljedećeg:
1. p A X - zaposlenik označen brojem A povećava (ili smanjuje ukoliko je X negativan) plaću svima sebi podređenima za iznos X (-10 000 ≤ X ≤ 10 000);
2. u A - Mirka zanima plaća zaposlenika označenog brojem A.
OutputNa standardni izlaz za svaki upit o plaći ispišite odgovarajući broj.
Input:
2 3
5
3 1
p 1 5
u 2
u 1Output:8
5Input:
5 5
4
2 1
6 1
7 1
3 4
u 3
p 1 -1
u 3
p 4 5
u 5Output:6
5
7Input:
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 1Output:7
9
7
5Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.