310612: CF1859F. Teleportation in Byteland

F. Teleportation in Bytelandtime limit per test8 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

There are $n$ cities in Byteland, some of which are connected by roads, which can be traversed in any direction. The $i$-th road has its own hardness parameter $w_i$. Time spent on traversing a road with its hardness equal to $w_i$ is $\lceil\frac{w_i}{c}\rceil$, where $c$ is the current driving skill.

The travel network of Byteland is a tree. In other words, between any pair of cities, there is exactly one path that passes through each city at most once.

In some cities you can visit driving courses. A single course takes $T$ time to complete, and after completing the course the driver's skill $c$ is increased by $2$ times. Notice that the time $T$ required to complete a course is the same in all cities, and courses can be completed in the same city more than once.

You need to answer the $q$ queries: what is the minimum time it takes to get from the city $a$ to city $b$ if you start the travelling with driving skill $c = 1$?

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $T$ ($1 \le n \le 10^5, 1 \le T \le 10^6$) - the number of cities and time required to complete a single driving course.

The following $n - 1$ lines each contain three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^6, u_i \neq v_i$), which mean that there exists a road connecting towns $u_i$ and $v_i$ with hardness equal to $w_i$ .

The next line contains a binary string $s$ of length $n$, consisting only of symbols $0$ and $1$. If $s_i = 1$ ($1 \le i \le n$), then you can visit driving courses in the $i$-th city. If $s_i = 0$ ($1 \le i \le n$), then you cannot visit driving courses in the $i$-th city.

The next line contains a single integer $q$ ($1 \le q \le 10^5$) — the number of queries you are required to answer.

The next $q$ lines contain two integers $a_j$, $b_j$ ($1 \le a_j, b_j \le n, 1 \le j \le q$) — the cities you are required to process in the $j$-th query.

It is guaranteed that the given graph is a tree. It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases does not exceed $10^5$.

Output

For each query, print one integer in a separate line — the minimum time it takes to get in the corresponding query.

ExampleInput

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

Output

1
11
14
11
13
15

Note

In the only query of the first test case, it is optimal to ignore the driving courses. Then the minimum time required is equal to the distance between vertexes $1$ and $2$, which is $1$.

In the first query of the second test case, we can spend $3$ time in city number $1$ visiting the driving courses, then go to vertex $5$. Then the minimum time required is $3 + \lceil\frac{5}{2}\rceil + \lceil\frac{10}{2}\rceil = 11$.

**题目大意：**
在比特兰德有 $ n $ 个城市，某些城市之间通过道路相连，道路可以双向通行。每条道路有一个硬度参数 $ 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 $。

**输出数据格式：**
对于每个查询，打印一行一个整数 — 对应查询所需的最短时间。**题目大意：** 在比特兰德有 $ n $ 个城市，某些城市之间通过道路相连，道路可以双向通行。每条道路有一个硬度参数 $ 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 $。 **输出数据格式：** 对于每个查询，打印一行一个整数 — 对应查询所需的最短时间。