Codeforces Round 892 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dfs and similar

divide and conquer

graphs

shortest paths

trees

*3200

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Teleportation in Byteland

time limit per test

8 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere 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.

Example

Input

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 11:37:15 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|