题目描述

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

输入描述

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

1. 第一行：一个整数 ( N ) ，表示树的节点总数
2. 接下来 ( N - 1 ) 行：每行三个整数 ( a_i\ b_i\ c_i ) ，描述树的一条边，其中 ( a_i ) 和 ( b_i ) 是边连接的两个节点，( c_i ) 是这条边的权值
3. 然后一行：两个整数 ( Q\ K ) ，分别表示查询的数量和固定的中转节点
4. 最后 ( Q ) 行：每行两个整数 ( x_j\ y_j ) ，表示第 ( j ) 次查询的起点和终点

数据范围

• 树的节点总数 ( N )：( 3 \leq N \leq 10^5 )
• 树边的端点 ( a_i, b_i )（用于描述第 ( i ) 条边 ）：( 1 \leq a_i, b_i \leq N )（( 1 \leq i \leq N - 1 ) ，因为树有 ( N - 1 ) 条边 ）
• 树边的权值 ( c_i )：( 1 \leq c_i \leq 10^9 )（( 1 \leq i \leq N - 1 ) ）
• 查询的数量 ( Q )：( 1 \leq Q \leq 10^5 )
• 中转节点 ( K )：( 1 \leq K \leq N )
• 查询中起点 ( x_j ) 和终点 ( y_j )（第 ( j ) 次查询 ）：( 1 \leq x_j, y_j \leq N )（( 1 \leq j \leq Q ) ）
• 额外限制（针对每次查询 ）：( x_j \neq y_j )（( 1 \leq j \leq Q ) ）；( x_j \neq K ) 且 ( y_j \neq K )（( 1 \leq j \leq Q ) ）
• 给定的图是一棵树（无环且连通 ）

输出描述

输出共 ( Q ) 行，对于第 ( j )（( 1 \leq j \leq Q ) ）行，输出第 ( j ) 次查询的结果，即节点 ( x_j ) 经过中转节点 ( K ) 到节点 ( y_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

样例输入 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

样例输入 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