Chef and Path

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has a tree (with N nodes, numbered from 1 to N) where each edge has some length.
The Chef length of a path is the median of the lengths of all edges along the path. More formally: if we put lengths of all edges from the path into an array and sort it, then the Chef length of this path is the median of this array (element in the middle of the sorted array, and if we have two elements in the middle of the array, then the median is the bigger one). For example, if the array equals {3, 7, 9}, then its median is 7, and if the array equals {1, 2, 3, 4}, then the median is 3.
Now, Chef wants to find minimum Chef length among simple paths having at least L and at most R edges. Please help him accomplish this task.
Input
 The first line of input contains an integer T denoting the number of test cases. Description of T test cases follows.
 The first line for a test case contains three spaceseparated integers  N, L, R  denoting the number of nodes in a tree, and the limits on number of edges in any chosen path.
 Each of next N − 1 lines contains three spaceseparated integers  a, b and c  describing an edge in the tree. This edge connects vertex a with vertex b and has length c.
Output
For each test case, output a single line containing the shortest Chef length amongst paths satisfying the given conditions. If there are no paths with at least L and at most R edges, output 1.
Constraints
 1 ≤ T ≤ 5×10^{4}
 2 ≤ N ≤ 10^{5}
 2 ≤ L ≤ R ≤ 50
 1 ≤ a, b ≤ N
 1 ≤ c ≤ 10^{9}
 The sum of N over all the test cases in one file is at most 3×10^{5}
 The given graph denotes a tree
Subtasks
Subtask 1 (27 points)
 The sum of N over all the test cases in one file is at most 1000
 Time Limit is 1 second
Subtask 2 (73 points)
 Original constraints
 Time Limit is 6 seconds
Example
Input: 2 6 2 3 1 3 3 1 2 1 2 4 1 2 5 2 3 6 2 5 3 4 1 2 3 2 3 1 3 4 4 4 5 2 Output: 1 2
Explanation
Test #1
Let's look at all correct simple paths:
 136, lengths = {3, 2} => Chef length = 3
 124, lengths = {1, 1} => Chef length = 1
 125, lengths = {1, 2} => Chef length = 2
 213, lengths = {1, 3} => Chef length = 3
 2136, lengths = {1, 3, 2} => Chef length = 2
 425, lengths = {1, 2} => Chef length = 2
 4213, lengths = {1, 1, 3} => Chef length = 1
 5213, lengths = {2, 1, 3} => Chef length = 2
And the reverse of these paths. So, the smallest value we get is 1 and it is the answer.
Test #2
All correct paths:
 1234, lengths = {1, 3, 4} => Chef length = 3
 2345, lengths = {1, 2, 4} => Chef length = 2
 12345, lengths = {1, 2, 3, 4} => Chef length = 3
The shortest Chef length is 2.
Note
A simple path in a graph is a path which does not have any repeated vertices.
Author:  antoniuk1 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/STETSKLX 
Tags  antoniuk1, aug15, binarysearch, divideandconq, mediumhard, minimumquery, slidingrange, unrootedtrees 
Date Added:  17072015 
Time Limit:  1  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 