У Васи есть дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. Изначально в каждой вершине записано число $$$0$$$.
Определим $$$d(i, j)$$$ как расстояние между вершинами $$$i$$$ и $$$j$$$ в дереве, то есть количество ребер на кратчайшем пути из $$$i$$$ в $$$j$$$. Также определим поддерево глубины $$$k$$$ вершины $$$x$$$ — набор вершин $$$y$$$, таких, что выполняются следующие условия:
Васе нужно обработать $$$m$$$ запросов к дереву. $$$i$$$-й запрос представляется тремя числами $$$v_i$$$, $$$d_i$$$ и $$$x_i$$$, и означает, что Васе нужно прибавить значение $$$x_i$$$ ко всем вершинам поддерева вершины $$$v_i$$$ на глубине $$$d_i$$$.
Сообщите Васе значение, записанное в каждой вершине после обработки всех запросов.
Первая строка содержит число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество вершин в дереве.
Следующие $$$n - 1$$$ строк содержат по два числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$), представляющие ребро между вершинами $$$x$$$ и $$$y$$$. Гарантируется, что данные ребра составляют дерево.
Следующая строка содержит число $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — количество запросов.
Следующие $$$m$$$ строк содержат по три числа $$$v_i$$$, $$$d_i$$$, $$$x_i$$$ ($$$1 \le v_i \le n$$$, $$$0 \le d_i \le 10^9$$$, $$$1 \le x_i \le 10^9$$$) — описание $$$i$$$-го запроса.
В единственной строке выведите $$$n$$$ чисел. $$$i$$$-е число должно равняться значению, записанному в $$$i$$$-й вершине после обработки всех запросов.
5 1 2 1 3 2 4 2 5 3 1 1 1 2 0 10 4 10 100
1 11 1 100 0
5 2 3 2 1 5 4 3 4 5 2 0 4 3 10 1 1 2 3 2 3 10 1 1 7
10 24 14 11 11
В первом тестовом примере изначально значения в вершинах равны $$$0, 0, 0, 0, 0$$$. После первого запроса значения будут равны $$$1, 1, 1, 0, 0$$$. После второго запроса значения будут равны $$$1, 11, 1, 0, 0$$$. После третьего запроса значения будут равны $$$1, 11, 1, 100, 0$$$.
Название |
---|