CF1399E1.Weights Division (easy version)

Easy and hard versions are actually different problems, so we advise you to read both statements carefully.

You are given a weighted rooted tree, vertex $1$ is the root of this tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a vertex $v$ is the last different from $v$ vertex on the path from the root to the vertex $v$. Children of vertex $v$ are all vertices for which $v$ is the parent. A vertex is a leaf if it has no children. The weighted tree is such a tree that each edge of this tree has some weight.

The weight of the path is the sum of edges weights on this path. The weight of the path from the vertex to itself is $0$.

You can make a sequence of zero or more moves. On each move, you select an edge and divide its weight by $2$ rounding down. More formally, during one move, you choose some edge $i$ and divide its weight by $2$ rounding down ($w_i := \left\lfloor\frac{w_i}{2}\right\rfloor$).

Your task is to find the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most $S$. In other words, if $w(i, j)$ is the weight of the path from the vertex $i$ to the vertex $j$, then you have to make $\sum\limits_{v \in leaves} w(root, v) \le S$, where $leaves$ is the list of all leaves.

You have to answer $t$ independent test cases.

简单版本和困难版本实际上是两个不同的问题，因此我们建议您仔细阅读两个版本的题面。

给定一棵带权有根树，其中顶点 $1$ 是这棵树的根。

树是一种无环的连通图。有根树具有一个特殊的顶点，称为根。顶点 $v$ 的父节点是指从根到 $v$ 的路径上最后一个不同于 $v$ 的顶点。顶点 $v$ 的子节点是指所有以 $v$ 为父节点的顶点。若一个顶点没有子节点，则称其为叶子节点。带权树是指该树的每条边均具有某个权重。

一条路径的权重定义为该路径上所有边的权重之和；从某顶点到其自身的路径权重为 $0$。

你可以执行零次或多次操作。每次操作中，你选择一条边，并将其权重向下取整除以 $2$。更准确地说，在一次操作中，你选择某条边 $i$，并令其权重更新为 $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$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $S$ ($2 \le n \le 10^5; 1 \le S \le 10^{16}$) — the number of vertices in the tree and the maximum possible sum of weights you have to obtain. The next $n-1$ lines describe edges of the tree. The edge $i$ is described as three integers $v_i$, $u_i$ and $w_i$ ($1 \le v_i, u_i \le n; 1 \le w_i \le 10^6$), where $v_i$ and $u_i$ are vertices the edge $i$ connects and $w_i$ is the weight of this edge.

It is guaranteed that the sum of $n$ does not exceed $10^5$ ($\sum n \le 10^5$).

输入的第一行包含一个整数 $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$ 是该边所连接的两个顶点，$w_i$ 是该边的权重。

保证所有测试用例的 $n$ 之和不超过 $10^5$（即 $\sum n \le 10^5$）。

For each test case, print the answer: the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most $S$.

对于每个测试用例，输出答案：使从根节点到每个叶子节点的路径权重之和均不超过 $S$ 所需的最少移动次数。