#Duck006. [DuckOI]Kill the Duck

[DuckOI]Kill the Duck

题目描述

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跑到了一个有nn个结点,n1n-1条边的树上

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

XCR现在有mm次询问,第i(1im)i(1 \leq i \leq m)次给出两个正整数xix_iyiy_i,含义如下

DengDuck 在点 xi(1xin)x_i(1 \leq x_i \leq n) 上,XCR在点 yi(1yin)y_i(1 \leq y_i \leq n)

对于每次询问,请问XCR离DengDuck的距离是多少?

输入格式

第一行一个整数nn

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

n+1n+1行一个正整数mm

接下来mm行每行两个正整数xix_iyiy_i

输出格式

mm行,每行一个正整数,表示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,mn,m的范围 特殊限制
5%5\%的数据 1201~20
20%20\%的数据 130001~3000
另外的5%5\%的数据 m=1m=1
所有数据 11000001~100000