思路分析

题目要求在树上进行一次或多次结点扩展（每个结点最多扩展一次），以尽量增加某一层的宽度。宽度的定义是某一深度层上的结点数。

核心观察：

1. 层数统计：用 BFS（或 DFS）可以求出每一层的结点集合及其扩展代价。
2. 扩展策略：扩展某层的结点，只会在该层下一层新增结点，从而可能提高下一层的宽度。
3. 资源限制：总魔力值 k，扩展代价不同，等价于一个“0-1 背包”优化，但因为每层独立计算，只需要对每层进行“贪心”。

题目内容

给定一棵以 $1$ 为根节点的树。该树共有 $n$ 个节点，你现在拥有魔力值 $k$ 。你可以以进行以下操作任意次(每个节点最多进行一次，新生成的节点不能再进行操作)：

• 选择一个节点 $i$ ，消耗 $a_i$ 的魔力值，使节点 $i$ 长出一个子节点。

你的目标是使树的宽度最大化（树的宽度定义为某一深度上节点数的最大值）。请你输出能够达到的最大宽度。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^4)$ ，表示数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,k(1≦n,k≦10^5)$ ,分别表示树的节点数量和拥有的魔力值。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦10^5)$ ，其中 $a_i$ 表示节点 $i$ 进行扩展操作所需的魔力值。

接下来 $n-1$ 行，第 $i$ 行输入两个整数 $u_i,v_i(1≦u_i,v_i≦n;u_i≠v_i)$ ，表示第 $i$ 条边连接节点 $u_i$ 与节点 $v_i$ ，保证给定的 $n$ 个节点构成一棵树。

除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$ 。

输出描述

对于每组测试数据，新起一行，输出一个整数，表示树的最大宽度。

样例1

输入

1
3 5
1 2 7
1 2
2 3

输出

2

说明

在此样例中，原始树为链 $1-2-3$ 。可以在节点 $1$ 扩一次；或在节点 $2$ 扩一次；也可以同时在二者各扩一次。最大宽度均为 $2$ 。