A16110 | Teleportation in Byteland

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

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

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