Опасность
Опасность
Задано неориентированное дерево с n вершинами, ребрам которого присвоены веса. Необходимо выполнить запросы двух типов:
- Прибавить значение
ai
ко всем ребрам на пути от вершиныvi
до вершиныui
. Этого типа имеется не более 500 запросов. - Вычислить сумму весов всех ребер, оба конца которых находятся на расстоянии не более
ki
отvi
. Расстояние между двумя вершинами равно числу ребер на пути между ними.
Выполнять запросы следует в указанном порядке. Для каждого запроса второго типа вывести найденное значение.
Входные данные
Первая строка содержит два числа n и q (1 ≤ n ≤ 1000, 0 ≤ q ≤ 500000) - количество вершин в дереве и количество запросов. Следующая n - 1 строка содержит описание дерева: i-ая строка содержит три числа vi
, ui
и wi
(1 ≤ vi
, ui
≤ n, 1 ≤ wi
≤ 100000) - номера вершин, соединенных ребром, и его вес. Гарантируется, что граф является деревом.
Следующие q строк описывают запросы. В этих строках первым числом ti
является тип запроса (1 ≤ ti
≤ 2). Если ti
= 1, то далее следуют три числа vi
, ui
и ai
(1 ≤ vi
, ui
≤ n, 1 ≤ ai
≤ 100000), означающих что надо добавить ai
ко всем ребрам на пути от vi
до ui
. Если ti
= 2, то далее следуют два числа vi
и ki
(1 ≤ vi
≤ n, 1 ≤ ki
≤ n), означающих что надо найти сумму весов всех ребер, концы которых находятся на расстоянии не больше ki
от вершины vi
. Гарантируется, что запросов первого типа не более 500.
Выходные данные
Для каждого запроса второго типа вывести в отдельной строке ответ на него.
5 5 1 2 1 2 3 2 3 4 3 3 5 1 2 2 1 2 4 2 1 1 4 2 2 1 2 2 3 3
3 6 7 13