← 返回题目列表

Codeforces · 1859/F

F. Byteland 的传送

中文机器翻译题面 查看原题

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$$$。