2161 . 只走一次
TopCoder
Tags
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 1
3 3
1 2 1
2 3 1
1 2
1 3
1 2
1 2 1
2 3 1
1 2
1 3
1 2
Sample Output 1
1
1
0
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 |