CF1399E2 Weights Division (hard version)

简单版和困难版实际上是不同的问题，因此建议你仔细阅读两者的题面。 给定一棵带权有根树，顶点 $1$ 是这棵树的根。每条边都有自己的代价。 树是一个无环连通图。有根树有一个特殊的顶点称为根。顶点 $v$ 的父亲是从根到顶点 $v$ 路径上最后一个不同于 $v$ 的顶点。顶点 $v$ 的所有子节点是以 $v$ 为父亲的所有顶点。如果一个顶点没有子节点，则称其为叶子。带权树是指树中每条边都有一个权值。 一条路径的权值是该路径上所有边的权值之和。从某个顶点到自身的路径权值为 $0$。 你可以进行若干次操作（可以为零次）。每次操作，你可以选择一条边，将其权值除以 $2$ 并向下取整。更正式地说，每次操作你选择某条边 $i$，将其权值变为 $w_i := \left\lfloor\frac{w_i}{2}\right\rfloor$。 每条边 $i$ 有一个代价 $c_i$，为 $1$ 或 $2$ 个金币。每次对边 $i$ 进行操作需要花费 $c_i$ 个金币。 你的任务是，最小化总花费，使得从根到每个叶子的路径权值之和不超过 $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$ 和 $c_i$ 描述（$1 \le v_i, u_i \le n; 1 \le w_i \le 10^6; 1 \le c_i \le 2$），表示该边连接的两个顶点、权值和代价。 保证所有测试用例中 $n$ 的总和不超过 $10^5$（$\sum n \le 10^5$）。

对于每个测试用例，输出一行答案：使得从根到每个叶子的路径权值之和不超过 $S$ 所需的最小总花费。

由 ChatGPT 4.1 翻译