3-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"D" Дерево и многочлены
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Ник учится на первом курсе. На курсе алгоритмов он изучает деревья. На курсе алгебры Ник изучает многочлены. А еще Ник очень любит прменять увиденное. Недавно он придумал задачу, но никак не может ее решить. Помогите ему.

Дано подвешенное дерево с n вершинами, пронумерованными от 1 до n. Исходно в каждой вершине дерева записано число 0. Для вершины v обозначим как d[v] глубину вершины v — количество вершин на пути от корня дерева до вершины v, в частности корень имеет глубину 1.

Дано число k. Требуется обрабатывать запросы двух видов.

  1. Дана вершина v и многочлен q(t) = q0 + q1t + q2t2 + ... + qktk. Для каждой вершины u в поддереве вершины v требуется прибавить к значению в этой вершине значение q(d[u]).
  2. Дана вершина v и многочлен q(t) = q0 + q1t + q2t2 + ... + qktk. Для каждой вершины u на пути от корня до вершины v, включительно, требуется прибавить к значению в этой вершине значение q(d[u]).

Все действия выполняются по модулю 109 + 7.

Помогите Нику понять, какие числа будут записаны в вершинах дерева после выполнения всех операций.

Формат входных данных

Входные данные содержат несколько тестов. В первой строке задано число t — количество тестов (1 ≤ t ≤ 105).

Далее следует описание тестов. Описание теста начинается с числа n — количества вершин в дереве, и числа k — максимальной степени многочленов (1 ≤ n ≤ 105, 1 ≤ k ≤ 20).

Далее следует n чисел p1, p2, ..., pn, число pi задает номер родителя вершины i, либо равно 0, если вершина i является корнем. Гарантируется, что числа pi задают корректное подвешенное дерево.

Следующая строка содержит число q — количество запросов (1 ≤ q ≤ 105). Следующие q строк содержат запросы, описание запроса состоит из числа t, равного 1 или 2 — типа запроса, после которого следует число v — номер вершины, и затем k + 1 целое число q0, q1, ..., qk — коэффициенты многочлена (0 ≤ qi < 109 + 7).

Гарантируется, что сумма значений n во всех тестов одних входных данных не превышает 105. Также сумма значений q во всех тестов одних входных данных не превышает 105.

Формат выходных данных

Для каждого теста выведите n чисел, для каждой вершины выведите число, которое в ней окажется после выполнения всех запросов. Еще раз напомним, что все вычисления проводятся по модулю 109 + 7.

Примеры
Входные данные
1
4 2
2 4 2 0
3
1 2 0 1 0
2 3 1 0 0
2 1 0 0 1
Выходные данные
12 7 4 2
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.