eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дерево

Дерево

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

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

Вхідні дані

В первой строке содержится число вершин в дереве n (1n40000). В следующих n строках пары чисел p_i и v_i (0i < n). p_i — номер предка вершины с номером i, если p_i = -1, то эта единственная вершина является корнем. v_i — число, записанное в вершине (0v_i10^6).

Вихідні дані

Выведите единственное число

помодулю P. i — множество индексов внутренних вершин, a_i — ответы для них (q = 127, P =1000000007).

Приклад

Вхідні дані #1
3
-1 1
0 2
0 2
Вихідні дані #1
0
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь