Задача №114320. Взлом сейфа
Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.
Она организована как подвешенное за вершину 0 дерево из \(n\) (\(1 \le n \le 20000\)) вершин, каждая из которых требует цифру от \(0\) до \(9\). Вершины пронумерованы от \(0\) до \(n - 1\).
Единственная информация, которой владеют коровы – что определённые последовательности длины \(5\) не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.
По заданным \(m\) (\(0 \le m \le 50000\)) последовательностям длины \(5\), вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.
Вы должны выводить свой ответ по модулю \(1234567\).
Первая строка ввода содержит два разделённых пробелом целых числа, \(n\) и \(m\) (\(1 \le n \le 20000, 0 \le m \le 50000\)) - количество вершин в дереве и количество запрещённых последовательностей соответственно.
В последующих \(i\) строках находится описание дерева. Строка \(i + 1\) содержит одно целое число \(p[i]\), означающее родителя вершины \(i\) в дереве (\(0 \le p[i] \lt i\)).
В последующих \(m\) строках находится описание запрещённых последовательностей. Строка \(n + i\) содержит два целых числа \(v_i\) и \(s_i\), разделенные пробелом - стартовую вершину последовательности, и строку из \(5\) цифр, которая не встретится в шифре начиная с вершины \(v_i\) если двигаться вверх по дереву (\(0 \le v_i \lt n\)) соответственно.
Гарантируется, что корень дерева находится не менее чем в 4 шагах от \(v_i\).
Выведите единственное целое число – количество неподходящих конфигураций цифр по модулю \(1234567\).
Подзадача 1 (10 баллов): \(1 \le n \le 15, 0 \le m \le 15\)
Подзадача 2 (15 баллов): \(1 \le n \le 1000, 0 \le m \le 2000\)
Подзадача 3 (20 баллов): \(1 \le n \le 1000, 0 \le m \le 50000\)
Подзадача 4 (55 баллов): \(1 \le n \le 20000, 0 \le m \le 50000\)
6 2 0 1 2 3 3 4 01234 5 91234
19