#2783. [JLOI2012] 树

[JLOI2012] 树

题目描述

在这个问题中,给定一个值 ss 和一棵树。

在树的每个节点 ii 有一个权值 aia_i,问有多少条路径的节点权值总和为 ss

路径中节点的深度必须是升序的。

假设节点 11 是根节点,根的深度是 00,它的儿子节点的深度为 11

路径不必一定从根节点开始。

输入格式

第一行有两个整数 n,sn,s,其中 nn 是树的节点数。
第二行有 nn 个整数,第 ii 个整数 aia_i 表示节点 ii 的权值。
接下来的 n1n-1 行,每行有两个个整数 xxyy,表示 yyxx 的儿子。

输出格式

输出路径节点总和为 ss 的路径数量。

3 3
1 2 3
1 2
1 3
2

数据规模与约定

对于 100%100\% 的数据,1n1051\le n\leq 10^51s,ai1031\leq s,a_i\leq 10^3