Задачи
Подсчет на дереве
Подсчет на дереве
Задано дерево из n вершин, с каждой вершиной i связано число ai
(0 ≤ ai
≤ 1).
Назовем множество S вершин дерева прекрасным, если имеют место следующие условия:
- S не пустое.
- S связное. То есть если вершины u и v принадлежат S, то все вершины на простом пути между u и v также принадлежат S.
- Сумма всех
au
(u принадлежит S) равна k, где k - заданное число.
Вам следует подсчитать количество прекрасных множеств. Поскольку их число может быть большим, то ответ следует вывести по модулю 109
+ 7.
Входные данные
Первая строка содержит количество тестов t. Каждый тест состоит из следующих строк:
- первая строка содержит два целых числа n (1 ≤ n ≤ 50000) и k (1 ≤ k ≤ 100).
- Вторая строка содержит n целых чисел
a1
,a2
, ...,an
. - Каждая из следующих n - 1 строк содержит пары чисел u и v (1 ≤ u, v ≤ n) указывающих на наличие ребра между вершинами u и v. Гарантируется, что заданные ребра образуют дерево.
Выходные данные
Для каждого теста вывести ответ в отдельной строке.
Входные данные #1
3 3 1 1 0 1 1 2 1 3 5 2 0 1 0 1 1 1 2 1 3 1 4 2 5 3 0 1 1 0 1 2 2 3
Выходные данные #1
3 5 1