P16844 [GKS 2021 #B] Truck Delivery

Charles 是 Googleland 城市的一名卡车司机。Googleland 的结构是一棵有 $N$ 个节点的树，每个节点代表一个城市，每条边代表两个城市之间的道路。城市编号为 $1$ 到 $N$。Googleland 的首都是城市 $1$。每天，Charles 在城市 $C$ 装载重量为 $W$ 的货物，并希望沿城市间的唯一简单路径将货物运送到城市 $1$。每条道路 $i$ 设有一个通行费，如果货物重量大于或等于载重限制 $L_i$，则需支付金额 $A_i$。 Charles 工作 $Q$ 天，每天给出起点城市 $C$ 和货物重量 $W$。对于每天，求 Charles 当天支付的所有通行费的最大公约数。如果当天无需支付任何通行费，则答案为 $0$。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $Q$。 接下来的 $N-1$ 行描述道路。其中第 $i$ 行包含四个空格分隔的整数 $X$、$Y$、$L_i$ 和 $A_i$，表示连接城市 $X$ 和 $Y$ 的道路，其载重限制为 $L_i$，通行费为 $A_i$。 接下来的 $Q$ 行描述查询。其中第 $j$ 行包含两个空格分隔的整数 $C_j$ 和 $W_j$，表示第 $j$ 天的起点城市和货物重量。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是按顺序给出的 $Q$ 天答案列表，用空格分隔。

在样例 #1 中： - 第一天，Charles 需要支付道路 $(5, 3)$、$(3, 2)$ 和 $(2, 1)$ 的通行费。答案为 $\gcd(9, 8, 4) = 1$。 - 第二天，Charles 需要支付道路 $(3, 2)$ 和 $(2, 1)$ 的通行费。答案为 $\gcd(8, 4) = 4$。 - 第三天，Charles 无需支付任何通行费，因此答案为 $0$。 在样例 #2 中： - 第一天，Charles 需要支付道路 $(2, 1)$ 的通行费。答案为 $10$。 - 第二天，Charles 需要支付道路 $(3, 2)$ 和 $(2, 1)$ 的通行费。答案为 $\gcd(5, 10) = 5$。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le L_i \le 2 \times 10^5$。 对于所有 $i$，$1 \le A_i \le 10^{18}$。 所有 $L_i$ 互不相同。 对于所有 $j$，$2 \le C_j \le N$。 对于所有 $j$，$1 \le W_j \le 2 \times 10^5$。 保证给定的道路构成一棵树。 **测试集 1** $2 \le N \le 1000$。 $1 \le Q \le 1000$。 **测试集 2** 最多 $20$ 个测试用例满足 $2 \le N \le 5 \times 10^4$ 且 $1 \le Q \le 10^5$。 其余测试用例满足 $2 \le N \le 1000$ 且 $1 \le Q \le 1000$。 翻译由 DeepSeek V4 Pro 完成