← 返回题目列表

Codeforces · 1399/E1

E1. 重量除法(简易版)

中文机器翻译题面 查看原题

简单版和困难版实际上是不同的问题,所以我们建议您仔细阅读这两种说法。

给你一棵加权有根树,顶点 $$$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