--->
2 задач
<---
Источники
Дано дерево из n вершин. У каждой вершины есть цвет. Нужно обработать q запросов ( v i , c i ): найти расстояние от v i до ближайшей к v i вершины цвета c i . Расстоянием между вершинами называется минимальное количество рёбер в пути между ними.
На первой строке число n ( 1 ≤ n ≤ 10 5 ), следующая строка содержит числа p 1 , p 2 , ..., p n - 1 . 0 ≤ p i < i . p i – отец вершины i в дереве. Далее строка с числами a 0 , a 1 , ..., a n - 1 . 0 ≤ a i < n . a i – цвет вершины i . Далее строка с числом q ( 1 ≤ q ≤ 10 5 ). Следующие q строк содержат запросы v iq i ( 0 ≤ v i < n , 0 ≤ c i < n ).
Для каждого запроса выведите одно число – расстояние до ближайшей вершины нужного цвета, или - 1 , если в дереве нет вершин такого цвета.
5 0 1 1 3 1 2 3 2 1 9 0 1 0 2 0 3 1 0 2 1 2 2 3 3 3 1 4 2
0 1 2 -1 2 1 2 1 1
Рассмотрим следующую игру об удалении вершин из графа, представляющего лес (то есть объединение нескольких деревьев). Изначально граф состоит из одного дерева из n вершин, а количество очков равно 0 .
Игра задаётся перестановкой вершин и происходит следующим образом:
Просуммируем число очков по всем возможным n ! играм. Выведите это число по модулю 10 9 + 7 .
В первой строке входного файла дано число N ( 2 ≤ n ≤ 10 5 ) — количество вершин в исходном дереве.
Каждая из последующих N - 1 строк содержит два числа — x i , y i задающих концы соответствующего ребра дерева ( 1 ≤ x i , y i ≤ n ).
Выведите одно число — суммарное количество очков по модулю 10 9 + 7 .
Тесты к данной задаче состоят из 3 групп:
2 1 2
6
3 1 2 2 3
34