codeforces#P1859F. Teleportation in Byteland

    ID: 33993 远端评测题 8000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>data structuresdivide and conquergraphsshortest pathstrees

Teleportation in Byteland

Description

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.

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.

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