题目描述

XCR是世界名列前茅的OIer，今天在打模拟赛。

他已经AC了前四道题，准备暴切第五题，看着这个题面，突然发现不太对....

他一看五道题的名字

$$\mathtt{\color{red}{X}\color{black}{or}}\\ \mathtt{\color{red}{C}\color{black}{ount\;the\;Number\;of\;Dance\;Schemes}}\\ \mathtt{\color{red}{R}\color{black}{elaxing\;Time }}\\ \mathtt{\color{red}{A}\color{black}{n\; Easy\;Problem}}\\ \mathtt{\color{red}{K}\color{black}{ill\;the\;Duck}}\\ \mathtt{\huge{\color{red}{XCRAK}}} $$

XCR十分生气，想要杀了DengDuck

DengDuck跑到了一个有$n$个结点，$n-1$条边的树上

这个树的每个边都是无向的，都有边权

XCR现在有$m$次询问，第$i(1 \leq i \leq m)$次给出两个正整数$x_i$和$y_i$,含义如下

DengDuck 在点 $x_i(1 \leq x_i \leq n)$ 上,XCR在点 $y_i(1 \leq y_i \leq n)$ 上

对于每次询问，请问XCR离DengDuck的距离是多少？

输入格式

第一行一个整数$n$

接下来$n-1$行每行三个正整数分别表示一条边的起点，终点，边权

第$n+1$行一个正整数$m$

接下来$m$行每行两个正整数$x_i$和$y_i$

输出格式

有$m$行，每行一个正整数，表示DengDuck和XCR的距离

3
1 2 3
2 3 4
2

1 2
1 3

3
7

3
1 3 10
1 2 13
5
1 1
2 2
3 1
2 1
1 3

0
0
10
13
10

14
5 7 12
7 11 15
5 14 12
14 3 17
7 1 19
14 4 14
1 12 16
1 6 16
12 9 19
9 10 10
7 2 11
4 8 10
2 13 14
17
6 11
14 14
13 11
6 10
12 6
8 7
9 9
10 11
13 10
1 4
2 12
13 4
2 7
2 1
12 2
10 11
4 7

50
0
40
61
32
48
0
79
89
57
46
63
11
30
46
79
38

提示

对于一定的数据	$n,m$的范围	特殊限制
前$5\%$的数据	$1～20$	无
前$20\%$的数据	$1～3000$
另外的$5\%$的数据		$m=1$
所有数据	$1～100000$	无