题目描述

给出 n 个点的一棵树，多次询问两点之间的最短距离。

输入格式

第一行为3个整数 n, m, s。n 表示点数，m 表示询问次数，s表示根节点编号； 下来 n-1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k； 再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。 树中结点编号从 1 到 n。

输出格式

共 m 行，对于每次询问，输出一行询问结果。

样例

输入样例 1

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

输出样例 1

3
4

输入样例 2

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

输出样例 2

9
11
5

输入样例 3

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

输出样例 3

3
4

提示

数据范围：2 ≤ n ≤ 10^4 1 ≤ m ≤ 2 × 10^4 0 < k ≤ 100 1 ≤ x , y ≤ n 数据保证输入的描述可以构成树。

思路：欧拉序 + ST 表求LCA。 x,y两点距离 = dis[x] + dis[y] - 2*dis[lca(x,y)] 。