Byteland中有$$$n$$$个城市,其中一些城市之间有道路相连,可以向任何方向穿越。第 $$$i$$$ 路有自己的硬度参数 $$$w_i$$$。通过硬度等于 $$$w_i$$$ 的道路所花费的时间为 $$$\lceil\frac{w_i}{c}\rceil$$$,其中 $$$c$$$ 是当前的驾驶技能。
Byteland的旅游网络是一棵树。换句话说,任意一对城市之间,都恰好有一条路径最多经过每个城市一次。
在某些城市,您可以参加驾驶课程。完成单个课程需要 $$$T$$$ 时间,完成课程后,驾驶员的技能 $$$c$$$ 会提高 $$$2$$$ 倍。请注意,完成课程所需的时间 $$$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
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$$$。