Problem : 146 - 海綿寶寶之我家離你家多遠

Problem Statistics

Solved Member: 33　　Submission: 188　　User Tried: 35

Statement:

比奇堡的房子和道路形成了一棵樹〈亦即沒有環〉。
最近比奇堡流行一個話題：我家到某某人家有多遠。
　　珊迪：「我家到章魚哥家有多遠。」
　　蝦霸：「約莫是妳家到復活島的距離。」
現在，給你比奇堡的n間房子和其n-1個道路連接關係，並且給你q個詢問。
請你對每次詢問輸出兩間房子的距離。

Input:Output:

第一行有兩個數字n, q(1≦n≦100000, 1≦q≦100000)，代表總共有n間房子和q次詢問。
接下來有n-1行，每一行有三個數字a, b, c(1≦a,b≦n, 1≦c≦1000)，代表編號a與編號b的兩間房子之間有一條長度為c的雙向道路連接。
接下來有q行，每一行有兩個數字x, y，代表詢問編號x與編號y的兩間房子之間的距離。

請你對於每次詢問獨立輸出一行，包含一個數字，代表詢問的距離。

Sample Input:Sample Output:

5 2
1 2 1
2 3 4
2 4 8
1 5 2
1 5
3 5

2
7

HINT:

我愛海綿寶寶>///<

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	3000ms	65536kb
1	3000ms	65536kb	10
2	3000ms	65536kb	10
3	3000ms	65536kb	10
4	3000ms	65536kb	10
5	3000ms	65536kb	10
6	3000ms	65536kb	10
7	3000ms	65536kb	10
8	3000ms	65536kb	10
9	3000ms	65536kb	10
10	3000ms	65536kb	10