e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
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