简单版和困难版实际上是不同的问题,所以我们建议您仔细阅读这两种说法。
给你一棵加权有根树,顶点 $$$1$$$ 是这棵树的根。
树是没有循环的连通图。有根树有一个特殊的顶点,称为根。顶点 $$$v$$$ 的父节点是从根到顶点 $$$v$$$ 的路径上与 $$$v$$$ 顶点不同的最后一个顶点。顶点 $$$v$$$ 的子节点都是以 $$$v$$$ 为父节点的所有顶点。如果一个顶点没有子节点,那么它就是一个叶子。加权树是这样一种树,该树的每条边都有一定的权重。
路径的权重是该路径上边权重的总和。从顶点到自身的路径权重为$$$0$$$。
您可以进行一系列零次或多次移动。每次移动时,您选择一条边并将其权重除以向下舍入的 $$$2$$$。更正式地说,在一次移动过程中,您选择一些边 $$$i$$$ 并将其权重除以向下舍入的 $$$2$$$ ($$$w_i := \left\lfloor\frac{w_i}{2}\right\rfloor$$$)。
你的任务是找到使从根到每个叶子的路径权重之和最多为 $$$S$$$ 所需的最少移动次数。换句话说,如果 $$$w(i, j)$$$ 是从顶点 $$$i$$$ 到顶点 $$$j$$$ 的路径权重,那么你必须制作 $$$\sum\limits_{v \in leaves} w(root, v) \le S$$$,其中 $$$leaves$$$ 是所有叶子的列表。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含两个整数 $$$n$$$ 和 $$$S$$$ ($$$2 \le n \le 10^5; 1 \le S \le 10^{16}$$$) — 树中的顶点数以及您必须获得的最大可能的权重总和。接下来的 $$$n-1$$$ 行描述了树的边缘。边 $$$i$$$ 被描述为三个整数 $$$v_i$$$、$$$u_i$$$ 和 $$$w_i$$$ ($$$1 \le v_i, u_i \le n; 1 \le w_i \le 10^6$$$),其中 $$$v_i$$$ 和 $$$u_i$$$ 是边 $$$i$$$ 连接的顶点, $$$w_i$$$ 是这条边的权重。
保证 $$$n$$$ 的总和不超过 $$$10^5$$$ ($$$\sum n \le 10^5$$$)。
输出
对于每个测试用例,打印答案:使从根到每个叶子的路径权重之和最多为 $$$S$$$ 所需的最小移动次数。
示例
输入 #1
3 3 20 2 1 8 3 1 7 5 50 1 3 100 1 5 10 2 3 123 5 4 55 2 100 1 2 409
输出 #1
0 8 3