[JLOI2012] 树

题目描述

给你一棵以 1 为根的有根树。每个结点 (i) 有一个权值 (a_i)。

我们想统计有多少条"向下的路径"（从某个结点出发，不断走到它的子孙，结点深度严格递增），使得路径上结点权值之和等于 (s)。

路径可以从树上任意结点开始，并在它的任意后代结点结束；不要求必须从根出发，也不要求到叶子结束。 "深度升序"就是指沿着父→子→孙… 的方向走（不回头、不拐上去）。

输入格式

• 第一行：两个整数 (n, s) —— 结点数与目标和。
• 第二行：(n) 个整数，依次为 \(a_1, a_2, \dots, a_n\) —— 每个结点的权值。
• 接下来 (n-1) 行：每行两个整数 (x, y)，表示 (y) 是 (x) 的儿子（方向由父到子）。

输出格式

输出一个整数：权值和恰好为 (s) 的向下路径数。

输入输出样例 #1

输入 #1

3 3
1 2 3
1 2
1 3

输出 #1

2

解释

满足条件的两条路径为：

• \(1 \rightarrow 2\)，和为 (1+2=3)；
• 结点 (3) 自己（长度为 1 的向下路径），和为 (3)。

数据范围与约定

• \(1 \le n \le 10^5\)
• \(1 \le a_i, s \le 10^3\)

注：输入的 (n-1) 条边保证形成一棵以 1 为根的树；深度定义为：根的深度为 0，根的儿子深度为 1，依此类推。