Олимпиадный тренинг

Задача . E. Построение леса


Задача

Темы: графы снм Структуры данных *2000

Ориентированным взвешенным лесом называется взвешенный ациклический орграф, в котором из каждой вершины выходит не более одного ребра.

Корнем вершины v ориентированного взвешенного леса назовем вершину, из которой не выходит ребра, и до которой можно дойти из вершины v, двигаясь по ребрам ориентированного взвешенного леса. Обозначим корень вершины v как root(v).

Глубиной вершины v назовем сумму весов пути проходящего от вершины v до ее корня. Обозначим глубину вершины v как depth(v).

Рассмотрим процесс построения ориентированного взвешенного леса. Изначально лес не содержит вершин. Вершины последовательно добавляются по одной. Всего выполняется n операций добавления. i-я (i > 0) операция добавления описывается набором чисел (k,  v1,  x1,  v2,  x2,  ... ,  vk,  xk) и означает, что в граф нужно добавить вершину номер i и k ребер: ребро из вершины root(v1) в вершину i весом depth(v1) + x1, ребро из вершины root(v2) в вершину i весом depth(v2) + x2 и так далее. В случае, если k = 0, в граф добавляется только вершина i и не добавляется никаких ребер.

Ваша задача состоит в том, чтобы по заданным операциям добавления вершин вычислить остаток от деления суммы весов всех ребер леса, получившихся после применения всех заданных операций, на 1000000007 (109 + 7).

Входные данные

В первой строке записано единственное целое число: n (1 ≤ n ≤ 105) — количество операций добавления вершины.

Следующие n строк содержат описание операций, i-я из них содержит описание операции добавления i-ой вершины в следующем формате: первый числом строки является целое k (0 ≤ k ≤ i - 1), далее следует 2k целых чисел, разделенных пробелами: v1, x1, v2, x2, ... , vk, xk (1 ≤ vj ≤ i - 1, |xj| ≤ 109).

Операции заданы в том порядке, в котором их следует применять к графу. Гарантируется, что сумма k по всем операциям не превосходит 105, а также что в результате применения операций добавления вершин не образуется петель и кратных ребер.

Выходные данные

Выведите одно целое число — сумму весов всех ребер получившегося графа по модулю 1000000007 (109 + 7).

Примечание

Рассмотрим первый пример:

  1. Добавляется вершина 1. Так как k = 0, то ребер не добавляется.
  2. Добавляется вершина 2. Так как k = 0, то ребер не добавляется.
  3. Добавляется вершина 3. k = 1. v1 = 2, x1 = 1. Добавляется ребро из вершины root(2) = 2 в вершину 3 веса depth(2) + x1 = 0 + 1 = 1.
  4. Добавляется вершина 4. k = 2. v1 = 1, x1 = 5. Добавляется ребро из вершины root(1) = 1 в вершину 4 веса depth(1) + x1 = 0 + 5 = 5. v2 = 2, x2 = 2. Добавляется ребро из вершины root(2) = 3 в вершину 4 веса depth(2) + x1 = 1 + 2 = 3.
  5. Добавляется вершина 5. k = 1. v1 = 1, x1 = 2. Добавляется ребро из вершины root(1) = 4 в вершину 5 веса depth(1) + x1 = 5 + 2 = 7.
  6. Добавляется вершина 6. k = 1. v1 = 3, x1 = 4. Добавляется ребро из вершины root(3) = 5 в вершину 6 веса depth(3) + x1 = 10 + 4 = 14.

Получившийся граф показан на иллюстрации ниже:


Примеры
№Входные данныеВыходные данные
1 6
0
0
1 2 1
2 1 5 2 2
1 1 2
1 3 4 
30
2 5
0
1 1 5
0
0
2 3 1 4 3 
9

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет