#MX85. Christmas Tree

Christmas Tree

时间限制:2000ms

空间限制:1024MB

题目描述

圣诞节到了,小 Z 在圣诞树上挂满了彩球。

圣诞树一共有 nn 个节点,由 n−1n-1 条边进行连接,小 Z 在圣诞树的每个节点上都挂上了恰好一个彩球,其中第 ii 个节点上挂的彩球的美丽值为 aia_i。

小 Z 的幸运数字是 kk,因此小 Z 想把整棵圣诞树分成若干部分,每部分为树上的一个联通块,把其中每个彩球美丽值之和恰好为 kk 的联通块当作礼物送给他的朋友们。

小 Z 想知道他至多可以送出多少份礼物。

以下给出一份形式化的题意:

给定一棵 nn 个点的树和定值 kk,第 ii 个点的点权为 aia_i。

选出尽可能多的联通块,使得每个联通块之间的点不存在交集,且每个联通块内所有点的点权和恰为 kk。

输出可以选择的最多的联通块个数。

输入格式

第一行一个正整数 TT,表示数据组数,之后对于每组数据:

第一行给定两个整数 n,kn,k。

第二行给定 nn 个非负整数 a1,a2,...,ana_1,a_2,...,a_n。

之后 n−1n-1 行,每行给定两个整数 u,vu,v,表示树上的一条边。

输出格式

输出 TT 行,每行一个整数,表示答案。

样例 1 输入

4
7 5
1 2 1 2 2 1 2
1 2
2 3
3 4
3 5
5 6
5 7
2 2
1 0
1 2
1 1
1
1 2
1

样例 1 输出

2
0
1
0

样例 1 解释

对于第一组数据,选择的联通块分别为 {5,6,7},{2,3,4}\{5,6,7\},\{2,3,4\}。

样例 2,3 输入

见下发文件。

样例 2,3 输出

见下发文件。

数据规模与约定

对于 30%30\% 的数据,1≤∑i=1Tni≤200,1≤n≤201 \leq \sum_{i=1}^T n_i \leq 200,1 \leq n \leq 20。

对于 60%60\% 的数据,$1 \leq \sum_{i=1}^T n_i \leq 10^4,1 \leq n \leq 1000$。

对于 100%100\% 的数据,$1 \leq \sum_{i=1}^T n_i \leq 10^6,1 \leq k \leq 10^6,0 \leq a_i \leq 2$。