#3696. [JLOI2012]树

[JLOI2012]树

题目描述

在这个问题中,给定一个值 ss 和一棵树。在树的每个节点有一个权值,第 ii 个点的权值为 aia_i,问有多少条路径的节点权值总和为 ss。路径中节点的深度必须是升序的。假设节点 11 是根节点,根的深度是 00,它的儿子节点的深度为 11。路径不必一定从根节点开始。

输入格式

第一行有两个整数 nnss,其中 nn 是树的节点数。

第二行有 nn 个整数,第 ii 个整数 aia_i 表示节点 ii 的权值。

接下来的 (n1)(n-1) 行,每行有两个个整数 xxyy,表示 yyxx 的儿子。

输出格式

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

3 3
1 2 3
1 2
1 3
2

提示

数据规模与约定

  • 对于 100%100\% 的数据,保证 1n1051 \leq n \leq 10^51ai,s1031 \leq a_i, s \leq 10^3