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

Dynamic programming on Trees - Top Level

Подсчет на дереве

Задано дерево из n вершин, с каждой вершиной i связано число ai (0ai1).

Назовем множество S вершин дерева прекрасным, если имеют место следующие условия:

  • S не пустое.
  • S связное. То есть если вершины u и v принадлежат S, то все вершины на простом пути между u и v также принадлежат S.
  • Сумма всех au (u принадлежит S) равна k, где k - заданное число.

Вам следует подсчитать количество прекрасных множеств. Поскольку их число может быть большим, то ответ следует вывести по модулю 109 + 7.

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

Первая строка содержит количество тестов t. Каждый тест состоит из следующих строк:

  • первая строка содержит два целых числа n (1n50000) и k (1k100).
  • Вторая строка содержит n целых чисел a1, a2, ..., an.
  • Каждая из следующих n - 1 строк содержит пары чисел u и v (1u, vn) указывающих на наличие ребра между вершинами u и v. Гарантируется, что заданные ребра образуют дерево.

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

Для каждого теста вывести ответ в отдельной строке.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #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