e-olymp
Məsələlər

Дерево

Дерево

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

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

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

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

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

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
4
5 1 2 3 4 5
3 2 3 6
2 3 5
1 2
1 2
1 3
4 2
Çıxış verilənləri #1
10
Müəllif А. Миланин
Mənbə ACM, Ukraine, First Stage, 09.04.2011