## DISQUERY - Distance Query

The traffic network in a country consists of N cities (labeled with integers from 1 to N) and N-1 roads connecting

the cities. There is a unique path between each pair of different cities, and we know the exact length of each road.

Write a program that will, for each of the K given pairs of cities, find the length of the shortest and the length

of the longest road on the path between the two cities.

### Input

The first line of input contains an integer N, 2 ≤ N ≤ 100 000. Each of the following N-1 lines contains three

integers A, B and C meaning that there is a road of length C between city A and city B.
The length of each road will be a positive integer less than or equal to 1 000 000.
The next line contains an integer K, 1 ≤ K ≤ 100 000. Each of the following K lines contains two different

integers D and E – the labels of the two cities constituting one query.

```OutputEach of the K lines of output should contain two integers – the lengths from the task description for the corresponding pair of the cities. Sampleinput  5 2 3 100 4 3 200 1 5 150 1 3 50 3 2 4 3 5 1 2  output  100 200 50 150 50 100 input  7 3 6 4 1 7 1 1 3 2 1 2 6 2 5 4 2 4 4 5 6 4 7 6 1 2 1 3 3 5  output  2 6 1 4 6 6 2 2 2 6
```

hide comments
 < Previous 1 2 Next > aspro: 2017-06-26 15:32:45 very good question...also solve 609E(codeforces) Last edit: 2017-06-26 15:33:45 udit_003: 2017-04-10 22:53:30 AC in one go!! good problem must try Last edit: 2017-04-10 22:54:24 hamzaziadeh: 2016-09-18 23:24:08 So ez! AC in 1 go, good problem for noobs.. shas19: 2016-07-16 01:08:01 worked with HLD (even though it is an overkill) Luis Manuel Díaz Barón: 2015-04-23 17:08:02 It's true [20][100005] => ACCEPTED, [20][100005] => TLE The time limit is too tight. Nice question. Solved using LCA Mohammadreza Osouli: 2014-11-28 14:54:54 runtime error !! but i dont know why!!?? Ghost Of Perdition: 2013-05-24 01:00:18 very strict time limit .... why?? AC... Needs optimizations Last edit: 2013-05-24 06:36:30 darryl: 2011-11-28 11:40:45 Is HL-decomposition + sparse table enough? I keep getting TLE. 刘启鹏: 2010-01-05 12:38:19 remember [20][110000]==>AC [110000][20]==>TLE Tony Beta Lambda: 2009-06-22 10:59:01 An O(nlogn) algorithm is needed instead of the O(n(logn)^2) one against the new test data.

 Added by: ~!(*(@*!@^& Date: 2009-02-28 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: COI 06