题目描述

给出一棵有 $N$ 个结点的树，给出 $Q$ 个询问，求结点 $x_j$ 过结点 $K$ 到节点 $y_j$ 的最短距离。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个正整数 $a_i, b_i, c_i$，表示 $a_i$ 和 $b_i$ 之间的边权是 $c_i$。

接下来一行两个正整数 $Q, k$。

接下来 $Q$ 行，每行两个正整数 $x_j, y_j$，表示询问。

输出格式

输出 $Q$ 行，每行一个整数，回答一个询问。

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

3
2
4

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

5
14
22

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

17000000000

提示

• $3 \le N \le 10^5$
• $1 \le a_i​,b_i​\le N(1 \le i \le N-1)$
• $1 \le c_i​ \le 10^9(1 \le i \le N-1)$
• $1 \le Q \le 10^5$
• $1 \le K \le N$
• $1 \le x_j​,y_j​\le N(1 \le j \le Q)$
• $x_j ≠​y_j​(1 \le j \le Q)$
• $x_j​ ≠K,y_j​ ≠K(1 \le j \le Q)$