CF1859F Teleportation in Byteland

# 在比特兰的传送 比特兰有 $ n $ 个城市，其中一些城市由道路连接，道路可以双向通行。第 $ i $ 条道路有其自身的难度参数 $ w_i $。以难度为 $ w_i $ 的道路上的通行时间为 $ \lceil\frac{w_i}{c}\rceil $，其中 $ c $ 是当前驾驶技能。 比特兰的旅行网络是一棵树。换句话说，在任意两个城市之间，最多只有一条经过每个城市的路径。 在一些城市中，您可以参加驾驶课程。完成单个课程需要 $ T $ 时间，并且完成课程后驾驶员的技能 $ c $ 翻倍。请注意，完成课程所需的时间 $ T $ 在所有城市中是相同的，并且可以在同一个城市中多次完成课程。 您需要回答 $ q $ 个查询：如果您从技能 $ c = 1 $ 开始旅行，从城市 $ a $ 到城市 $ b $ 所需的最短时间是多少？

每个测试包含多个测试案例。第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）— 测试案例的数量。随后是测试案例的描述。 每个测试案例的第一行包含两个整数 $ n $ 和 $ T $（$ 1 \le n \le 10^5, 1 \le T \le 10^6 $）— 城市的数量和完成单个驾驶课程所需的时间。 接下来的 $ n - 1 $ 行，每行包含三个整数 $ u_i $，$ v_i $ 和 $ w_i $（$ 1 \le u_i, v_i \le n, 1 \le w_i \le 10^6, u_i \neq v_i $），表示存在一条连接城市 $ u_i $ 和 $ v_i $ 且难度为 $ w_i $ 的道路。 接下来一行包含一个长度为 $ n $ 的二进制字符串 $ s $，只包含符号 $ 0 $ 和 $ 1 $。如果 $ s_i = 1 $（$ 1 \le i \le n $），则您可以在第 $ i $ 个城市参加驾驶课程。如果 $ s_i = 0 $（$ 1 \le i \le n $），则您不能在第 $ i $ 个城市参加驾驶课程。 接下来一行包含一个整数 $ q $（$ 1 \le q \le 10^5 $）— 您需要回答的查询数量。 接下来的 $ q $ 行，每行包含两个整数 $ a_j $，$ b_j $（$ 1 \le a_j, b_j \le n, 1 \le j \le q $）— 您需要在第 $ j $ 个查询中处理的城市。 保证给定的图是一棵树。保证所有测试案例中 $ n $ 和 $ q $ 的总和不超过 $ 10^5 $。

对于每个查询，打印一个整数，表示相应查询所需的最短时间。 ## 样例 #1 ### 样例输入 #1 ``` 2 2 3 1 2 1 11 1 1 2 5 3 1 4 5 1 3 8 2 3 8 4 5 10 11001 5 1 5 2 5 5 1 3 4 4 2 ``` ### 样例输出 #1 ``` 1 11 14 11 13 15 ```

在第一个测试案例的唯一一个查询中，最优的策略是忽略驾驶课程。然后，所需的最短时间等于顶点 $ 1 $ 到顶点 $ 2 $ 之间的距离，即 $ 1 $。 在第二个测试案例的第一个查询中，我们可以在城市号为 $ 1 $ 花费 $ 3 $ 时间参加驾驶课程，然后前往顶点 $ 5 $。然后，所需的最短时间为 $ 3 + \lceil\frac{5}{2}\rceil + \lceil\frac{10}{2}\rceil = 11 $。