Сумма пути от корня
Вам дано дерево из
n узлов. Для i-го узла задано значение (0 ≤ a_i ≤ 10^9). Ваша задача — найти количество путей в дереве, которые начинаются в корневом узле и имеют сумму, равную заданному значению s.Ввод
В первой строке находятся два целых числа, разделённые пробелом:
n и s (1 ≤ n ≤ 10^5, 0 ≤ s ≤ 10^9), которые обозначают количество узлов в дереве и целевую сумму соответственно.
Во второй строке содержатся n целых чисел, разделённых пробелами, — до (0 ≤ a_i ≤ 10^9), задающие значения, ассоциированные с каждым узлом дерева.
Последующие n-1 строк описывают рёбра дерева. В каждой из этих строк содержится по два целых числа a и b (1 ≤ a, b ≤ n), разделённые пробелом, означающие ребро между узлами a и b. Гарантируется, что заданные рёбра образуют дерево.Вывод
Выведите одно целое число — количество путей в дереве, которые начинаются в корневом узле и имеют сумму, равную значению
s.Пример
Ввод | Вывод |
5 6
1 2 3 4 5
1 2
2 3
1 5
5 4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB