解题思路

扩编某个节点只会在它的下一层新增一个节点，从而可能提高下一层的宽度。每个原有节点最多扩编一次，额度总量为 $k$ 。

先 BFS 求出每一层节点及其扩编消耗。对每一层独立贪心：按消耗从小到大选择，能扩多少扩多少，直到额度不够。该层原始宽度、以及“下一层原始节点数加上本层扩编个数”，都是宽度候选。取所有候选的最大值。

各层额度按“只用本层”来计算时，使用的是同一份总额度 $k$ （扩编只发生在一层上以抬高下一层，不同层的扩编不会同时用来抬高同一层，贪心取全局最大即可）。

复杂度分析

一棵以节点 1 为根、共有 $n$ 个节点的树。你拥有额度 $k$ 。可以对节点进行扩编：选择一个节点 $i$ ，消耗 $a_i$ 额度，使它长出一个新的子节点。每个原有节点最多扩编一次，新长出的节点不能再扩编。

树的宽度定义为某一深度上节点个数的最大值。请输出在额度不超过 $k$ 的前提下能达到的最大宽度。

约束：测试组数不超过 10^4，单组节点数与额度均不超过 10^5，且单个测试文件中节点数之和不超过 10^5。扩编消耗为正整数且不超过 10^5。

每个测试文件包含多组数据。第一行一个整数 $T$ ，表示数据组数。