Skip to content

14363: 【原4363】Chika and Tree

题目

题目描述

author: Li Zitong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4363

Description

Chika 给你一个值 s 和一棵树。在树的每个结点有一个权值,第 i 个点的权值为 a_i 。

她想问你,树中结点权值总和为 s 的路径条数。路径中结点的深度要求升序。假设结点 1 是根结点,根的深度是 0,它的儿子结点的深度为 1。路径不必一定从根节点开始。

Input Format

第一行有两个整数 n (1 <= n <= 100000) 和 s (1 <= n <= 10^9),其中 n 是树的结点数。

第二行有 n 个整数,第 i 个整数 a_i (0 < a_i <= 1000) 表示结点 i 的权值。

接下来的 (n-1) 行,每行有两个个整数 x 和 y,表示 y 是 x 的儿子。

Output Format

输出路径权值总和为 s 的路径数量。

Sample Input 1

3 3
1 2 3
1 2
1 3

Sample Output 1

2

Sample Input 2

3 3
1 2 1
1 2
2 3

Sample Output 2

2

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!