Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Ёлочные украшения

(Время: 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.TXTOUTPUT.TXT
13 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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Атрибутика
 B. Боксёры
 C. Вечерний пейзаж города К
 D. Генные модификации
 E. Деревянный забор
 F. E равно эм це квадрат?
 G. Ёлочные украшения
 H. Железнодорожные тарифы
 I. Загадали? Угадаем!
 J. Искусство алхимии
 K. Йодакойн
 L. Клумбы

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru



доставка 1 кг