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.

Output

Each of the K lines of output should contain two integers – the lengths from the task description for the

corresponding pair of the cities.



Sample




input 

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
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 <O(NlogN), O(logN)>

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