Dynamic programming on Trees - Top Level
Дерево
Дано дерево. Для каждой вершины дерева есть набор элементов, которые можно помещать в данную вершину. Каждый элемент имеет вес - некоторое целое число. Для каждого ребра дерева определено отношение между вершинами, а именно, известно, в какой из двух вершин должен быть элемент с меньшим весом. Требуется определить количество различных способов выбрать в вершинах дерева по одному элементу, чтобы все отношения на ребрах соблюдались. Разные элементы из набора одной вершины могут иметь одинаковый вес.
Giriş verilənləri
В первой строке дано количество вершин n (1 ≤ n ≤ 1000) в дереве. Далее следуют n строк, в i-ой строке дан список допустимых элементов в вершине i. Строка начинается с целого числа k (1 ≤ k ≤ 1000) - количества элементов. Далее следуют k целых чисел w[j] (1 ≤ w[j] ≤ 10^9) - веса элементов.
В каждой из следующих n - 1 строке записаны два различных целых числа a и b (1 ≤ a, b ≤ n), которые означают, что в дереве есть ребро между вершинами a и b, и в вершине a должен быть размещен элемент меньшего веса, чем в вершине b.
Çıxış verilənləri
Вывести количество способов по модулю 1000000007.
Nümunə
4 5 1 2 3 4 5 3 2 3 6 2 3 5 1 2 1 2 1 3 4 2
10