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

Byteland 有 $n$ 座城市，其中部分城市通过双向道路相连。第 $i$ 条道路具有自身的硬度参数 $w_i$。 traversing 一条硬度为 $w_i$ 的道路所需时间为 $\lceil\frac{w_i}{c}\rceil$，其中 $c$ 为当前驾驶技能。

Byteland 的交通网络是一棵树。换言之，任意两座城市之间恰好存在唯一一条路径，且该路径至多经过每座城市一次。

在某些城市中可以参加驾驶培训课程。每门课程耗时 $T$，完成之后驾驶员的技能 $c$ 将变为原来的 $2$ 倍。注意：所有城市的课程耗时 $T$ 相同，且同一城市可多次参加课程。

你需要回答 $q$ 个查询：若从城市 $a$ 出发前往城市 $b$，且初始驾驶技能 $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$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

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

对于每个查询，在单独一行中输出一个整数——到达对应查询位置所需的最短时间。

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

在第一个测试用例的唯一查询中，最优策略是忽略驾驶课程。此时所需的最少时间为顶点 $1$ 与顶点 $2$ 之间的距离，即 $1$。

在第二个测试用例的第一个查询中，我们可在编号为 $1$ 的城市花费 $3$ 单位时间参加驾驶课程，然后前往顶点 $5$。此时所需的最少时间为 $3 + \lceil\frac{5}{2}\rceil + \lceil\frac{10}{2}\rceil = 11$。