DISQUERY  Distance Query
English  Vietnamese 
The traffic network in a country consists of N cities (labeled with integers from 1 to N) and N1 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 N1 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
changyouren:
20210930 11:04:32
use persistent segment tree + LCA


samarth5611:
20210907 13:45:52
I am getting Wrong answer on test Case 10,


nikhil0010:
20210713 20:26:50
solve codeforces 609E after this problem :) 

aldgebu:
20210322 16:47:25
I just print "answer" and I got 10 tests AC. have this task checker or something like that ? Whata fuck re you doin ?


rahul_raj8651:
20210205 12:28:00
AC, now back to hot sex with my goat. Last edit: 20210205 15:52:33 

pinku7499:
20200623 10:21:12
How simple...! 

shawnliang:
20191221 09:49:58
AC in 2s.why? 

abhimanyu_1998:
20190220 20:35:42
binary lifting should do the job


sarwar__05:
20180924 22:49:54
[100002][17] ==> AC in 0.70


vaibhav2303:
20180611 13:54:20
Simple sparse table(without binary search) and LCA concept gives AC. 
Added by:  ~!(*(@*!@^& 
Date:  20090228 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 06 