9539: 小塔的魔法树

小塔是一位年轻的魔法师，她发现了一棵神奇的魔法树。这棵树有 $n$ 个节点，每个节点上都刻有一个非负整数，代表着该节点蕴含的魔法能量。小塔想要选择一个包含根节点（编号为1）的连通子树，使得子树中所有节点的魔法能量总和不超过她的魔法容量 $m$。

给定一棵 $n$ 个节点的树，根节点为1，每个节点 $i$ 有一个非负整数权值 wiwi。你需要计算有多少种不同的包含根节点的连通子图，满足子图中所有节点的权值之和不超过 $m$。

形式上，你需要计算满足以下条件的节点集合 $S$ 的数量：

1. $1\in S$
2. $S$ 在树中形成的子图是连通的
3. ∑i∈Swi≤m∑i∈Swi≤m

第一行一个整数 $T$ 表示测试数据组数（$1\le T\le 5$）。

对于每组测试数据：

• 第一行两个整数 $n$ 和 $m$（1≤n≤5×1031≤n≤5×103, 1≤m≤5×1031≤m≤5×103）
• 第二行 $n$ 个整数 w1,w2,…,wnw1,w2,…,wn（0≤wi≤m0≤wi≤m）
• 接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示树的一条边。