Archiwum zadań programistycznych WWSI

Rosjanie odstąpili od swojego planu rozszczepienia systemu dróg Ukrainy na wiele części. Decyzja taka zapadła po jego dokładnym przeanalizowaniu. Ponumerowali oni miasta Ukrainy liczbami od 0 do n-1. Następnie nanieśli na mapie dokładnie n-1 dróg jakie pozostały na Ukrainie. Jak się okazało, system dróg ma postać drzewa. Z każdego miasta (wierzchołka) wychodzą co najwyżej dwie drogi (krawędzie). Wyjątkiem od tej reguły jest miejscowość o numerze 0, która to może być połączona z większą liczbą dróg.

Rosjanie szykują się do inwazji i potrzebują systemu do jej symulacji. System powinien realizować dwie operacje:

• 0 m z k zwiększa o z liczbę rosyjskich żołnierzy w mieście o numerze m oraz w każdej miejscowości oddalonej maksymalnie o k krawędzi od m.
• 1 m wyświetla aktualną liczbę rosyjskich żołnierzy znajdujących się w mieście m.

Twoim zadaniem jest oczywiście napisanie tego systemu.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [1;1000] i o ∈ [1;10⁴] oznaczające odpowiednio liczbę miast na Ukrainie oraz liczbę operacji do wykonania. W kolejnych n-1 liniach znajdują się opisy dwukierunkowych dróg jakie pozostały w tym kraju. Każdy opis drogi składa się z dwóch liczb a oraz b (0 ≤ a, b < n; a ≠ b) oznaczających miasta, które łączy. W następnych o liniach znajdują się operacje do wykonania. Mogą wystąpić dwa rodzaje poleceń, które to zostały opisane w treści zadania:

• 0 m z k gdzie m ∈ [0;n), z ∈ [1;1000], k ∈ [0;n].
• 1 m gdzie m ∈ [0;n).

Wyjście

Dla każdej operacji typu 1 należy wypisać aktualną liczbę rosyjskich żołnierzy znajdujących się w wybranym mieście m.

Przykład

Wejście

7 14
0 3
2 3
1 2
6 0
4 5
0 5
0 2 5 2
1 6
1 0
1 1
0 6 10 0
0 4 10 1
0 4 5 0
1 0
1 5
1 6
1 4
0 0 100 5
1 4
1 1

Wyjście

0
5
5
5
10
10
15
115
105