TopCoder

Thumb screenshot from 2022 02 07 14 53 28
FHVirus
到底要用哪一種 Code style 呢?

User's AC Ratio

93.3% (42/45)

Submission's AC Ratio

22.9% (56/245)

Description

哲哲最喜歡旅行了,但由於他荷包並沒有很胖,所以他只能在他所住的國家-ck國中旅行。ck國有$N$個城市(編號$1$到$N$),並且有$N-1$條雙向連接兩個城市的道路,其中第$j$條道路的長度為$w_j$。並且保證任兩個城市之間都可以藉由走一些道路從其中一個城市到達另一個。

哲哲安排了$Q$次旅行,其中第$i$次(依照時間先後排序)旅行,他打算從城市$a_i$走最短路徑到城市$b_i$,由於他想知道每次旅行大概要花多少時間,所以他請你幫他找出每次旅行最少所需要走的路徑長。

但是哲哲有一個特異功能:只要連接兩個城市之間所有的道路他都走過了,並且他在其中一個城市,他就可以瞬間移動到另一個城市(不需要走路)。

對了,他對自己的國家ck國很陌生,他一開始沒有走過任何一條路。

對!就是這樣,請你告訴哲哲每次旅行最少需要走多遠。

Input Format

輸入的第一行有兩個正整數$N,Q$,意義如題目所述,其中$1 \leq N,Q \leq 2\times 10^ 5$。
接下來的$N-1$行中,第$j$行中有三個整數$u_j,v_j,w_j$,代表ck國中存在一條連接編號為$u_j$的城市和編號為$v_j$的城市($1 \leq u_j,v_j \leq N$),長度為$w_j$的道路($1 \leq w_j \leq 1000$)。
再接下來的$Q$行中,第$i$中有兩個整數$a_i,b_i$,代表在第$i$次旅行中,哲哲打算從$a_i$走到$b_i$($1 \leq a_i,b_i \leq N$)。

Output Format

請輸出$Q$行,每行有一個整數,其中第$i$行的整數代表哲哲第$i$次旅行所需要走的最短路徑。

Sample Input

3 3
1 2 1
2 3 1
1 2
1 3
1 2

Sample Output

1
1
0

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~6 $N,Q \leq 20$ 10
2 7~13 對於每個城市最多只有兩條道路連接該城市和其他城市 21
3 14~20 $N,Q \leq 300$ 10
4 21~27 $N,Q \leq 2000$ 16
5 28~34 無其他限制 43

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1
1 2000 262144 65536 1
2 2000 262144 65536 1
3 2000 262144 65536 1
4 2000 262144 65536 1
5 2000 262144 65536 1
6 2000 262144 65536 1
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 3
15 2000 262144 65536 3
16 2000 262144 65536 3
17 2000 262144 65536 3
18 2000 262144 65536 3
19 2000 262144 65536 3
20 2000 262144 65536 3
21 2000 262144 65536 4
22 2000 262144 65536 4
23 2000 262144 65536 4
24 2000 262144 65536 4
25 2000 262144 65536 4
26 2000 262144 65536 4
27 2000 262144 65536 4
28 2000 262144 65536 5
29 2000 262144 65536 5
30 2000 262144 65536 5
31 2000 262144 65536 5
32 2000 262144 65536 5
33 2000 262144 65536 5
34 2000 262144 65536 5