e-olymp
Соревнования

Dynamic programming on Trees - Top Level

Дерево

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

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

В первой строке дано количество вершин n (1n1000) в дереве. Далее следуют n строк, в i-ой строке дан список допустимых элементов в вершине i. Строка начинается с целого числа k (1k1000) - количества элементов. Далее следуют k целых чисел wj (1wj109) - веса элементов.

В каждой из следующих n - 1 строке записаны два различных целых числа a и b (1a, bn), которые означают, что в дереве есть ребро между вершинами a и b, и в вершине a должен быть размещен элемент меньшего веса, чем в вершине b.

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

Вывести количество способов по модулю 1000000007.

Лимит времени 2 секунды
Лимит использования памяти 256 MiB
Входные данные #1
4
5 1 2 3 4 5
3 2 3 6
2 3 5
1 2
1 2
1 3
4 2
Выходные данные #1
10
Автор А. Миланин
Источник ACM, Ukraine, First Stage, 09.04.2011