Ёлочные украшения
(Время: 10 сек. Память: 64 Мб Сложность: 75%)
Вот, пришёл уже декабрь, а значит совсем уже скоро придёт время украшать новогоднюю ёлку. Байтика придумала новый способ
украсить свою ёлку – гирлянды-прогрессии.
Ёлка Байтики представляет собой дерево из N вершин, пронумерованных последовательными целыми числами от 0 до N–1. Изначально все вершины пусты.
В процессе украшения ёлки Байтика последовательно выполняет действия из следующего набора:
- 0 – Считает вес всех элементов гирлянд на вершинах из кратчайшего пути от вершины S до
вершины F включительно.
- 1 – Вешает на кратчайшем пути из вершины S в вершину F гирлянду-прогрессию, то есть в вершину на этом пути с расстоянием P до S вешает элемент гирлянды с весом A+P×D, где A и D – параметры гирлянды (для каждой гирлянды свои).
Ваша задача – промоделировать заданную последовательность действий.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и Q – количество вершин на ёлке Байтики и количество действий, соответственно (1 ≤ N, Q ≤ 105). Каждая из последующих N–1 строк содержит по два целых числа от 0 до N–1 – номера вершин, соединённых ребром. Гарантируется, что заданный этими строками граф является деревом.
Каждая из последующих Q строк содержит по одному действию. Действия задаются в порядке их совершения.
Действие типа 0 описывается тремя целыми числами 0 S F, где S и F – вершины, на кратчайшем пути между которыми требуется посчитать суммарный вес (0 ≤ S, F < N).
Действие типа 1 описывается пятью целыми числами 1 S F A D, где S – вершина, из которой Байтика начинает вешать гирлянду, F – вершина, в которой Байтика заканчивает вешать гирлянду, A и D – первый элемент и разность прогрессии,задающей гирлянду, соответственно (0 ≤ S, F < N, 0 ≤ A, D ≤ 105).
Выходные данные
Для каждого действия типа 0 в порядке их появления во входных данных в новой строке выходного файла OUTPUT.TXT выведите
одно число – остаток от деления требуемой суммы на 109+7.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 5
0 1
1 2
1 1 0 0 1
0 2 0
1 2 2 1 1
0 0 1
0 2 2 | 1
1
1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
