K-th value

There is a country with N cities.

These all cities are connected with roads and have no cycles.

Consider all simple paths whose lengths are between L and R (both inclusive).

Your task is to find the path that minimizes the k-th value of the path among them.

The k-th value of a simple path is “floor(length of path / k) + 1”-th value of the sorted length list of all roads in the path.

The first line contains a single integer T representing the number of test cases($1\leq T\leq 100$)
Sum of all $N\leq 700000$
The first line of each test case contains a single integer N.
Each of the following N – 1 lines contains 3 integers which represents two cities of the road and the length of the road.
Next lines contains 3 integers k, L, R.

$1\leq N \leq 10^5$
$1\leq a_i \leq 10^9$
$1 \leq L \leq R \leq 50$
$1<k<50$

Output the minimum k-th value of all simple paths whose length is between L and R.

If no such path exists output -1.

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

2

金策工业综合大学（DPRK）

2016 Multi-University Training Contest 9