题目描述

给定一棵具有 $N$ 个顶点的树。
这里，一个 树 是一种图形，更具体地说，是一个具有 $N-1$ 条边的连通无向图，其中 $N$ 是其顶点的数量。
第 $i$ 条边 $(1≤i≤N-1)$ 连接顶点 $a_i$ 和 $b_i$，并且长度为 $c_i$。

你还会收到 $Q$ 个查询和一个整数 $K$。在第 $j$ 个查询中 $(1≤j≤Q)$：

• 找到从顶点 $x_j$ 到顶点 $y_j$ 经过顶点 $K$ 的最短路径长度。

约束条件

• $3≤N≤10^5$
• $1≤a_i,b_i≤N (1≤i≤N-1)$
• $1≤c_i≤10^9 (1≤i≤N-1)$
• 给定的图是一棵树。
• $1≤Q≤10^5$
• $1≤K≤N$
• $1≤x_j,y_j≤N (1≤j≤Q)$
• $x_j≠y_j (1≤j≤Q)$
• $x_j≠K,y_j≠K (1≤j≤Q)$

输入

输入以以下格式从标准输入给出：

$N$
$a_1$ $b_1$ $c_1$
:
$a_{N-1}$ $b_{N-1}$ $c_{N-1}$ $Q$ $K$ $x_1$ $y_1$ :
$x_{Q}$ $y_{Q}$

输出

在 $Q$ 行中打印查询的响应。
第 $j$ 行 $j(1≤j≤Q)$，打印对第 $j$ 个查询的响应。

示例输入 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

示例输出 1

3
2
4

三个查询的最短路径如下：

• 查询 $1$：顶点 $2$ → 顶点 $1$ → 顶点 $2$ → 顶点 $4$ ：长度 $1+1+1=3$
• 查询 $2$：顶点 $2$ → 顶点 $1$ → 顶点 $3$ ：长度 $1+1=2$
• 查询 $3$：顶点 $4$ → 顶点 $2$ → 顶点 $1$ → 顶点 $3$ → 顶点 $5$ ：长度 $1+1+1+1=4$

示例输入 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

示例输出 2

5
14
22

每个查询的路径必须经过顶点 $K=2$。

示例输入 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

示例输出 3

17000000000