Freezing with Style

题意翻译

给定一颗带边权的树，求一条边数在 $[L,R]$ 之间的路径，并使得路径上边权的中位数最大。输出一条可行路径的两个端点。 注：此处 $1,2,3,4$ 的中位数为 $3$ ，而非 $2$ 或者 $2.5$ 。

题目描述

This winter is so... well, you've got the idea :-) The Nvodsk road system can be represented as $ n $ junctions connected with $ n-1 $ bidirectional roads so that there is a path between any two junctions. The organizers of some event want to choose a place to accommodate the participants (junction $ v $ ), and the place to set up the contests (junction $ u $ ). Besides, at the one hand, they want the participants to walk about the city and see the neighbourhood (that's why the distance between $ v $ and $ u $ should be no less than $ l $ ). On the other hand, they don't want the participants to freeze (so the distance between $ v $ and $ u $ should be no more than $ r $ ). Besides, for every street we know its beauty — some integer from $ 0 $ to $ 10^{9} $ . Your task is to choose the path that fits in the length limits and has the largest average beauty. We shall define the average beauty as a median of sequence of the beauties of all roads along the path. We can put it more formally like that: let there be a path with the length $ k $ . Let $ a_{i} $ be a non-decreasing sequence that contains exactly $ k $ elements. Each number occurs there exactly the number of times a road with such beauty occurs along on path. We will represent the path median as number $ a_{⌊k/2⌋} $ , assuming that indexation starting from zero is used. $ ⌊x⌋ $ — is number $ х $ , rounded down to the nearest integer. For example, if $ a={0,5,12} $ , then the median equals to $ 5 $ , and if $ a={0,5,7,12} $ , then the median is number $ 7 $ . It is guaranteed that there will be at least one path with the suitable quantity of roads.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ l $ , $ r $ ( $ 1\le l\le r,n\le 10^{5} $ ). Next $ n-1 $ lines contain descriptions of roads of the Nvodsk, each line contains three integers $ a_{i} $ , $ b_{i} $ , $ c_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ 0<=c_{i}<=10^{9} $ , $ a_{i}≠b_{i} $ ) — junctions $ a_{i} $ and $ b_{i} $ are connected with a street whose beauty equals $ c_{i} $ .

输出格式

Print two integers — numbers of the junctions, where to accommodate the participants and set up the contests, correspondingly. If there are multiple optimal variants, print any of them.

输入输出样例

输入样例 #1

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

输出样例 #1

4 1

输入样例 #2

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

输出样例 #2

6 3

输入样例 #3

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

输出样例 #3

4 3

输入样例 #4

8 3 6
1 2 9
2 3 7
3 4 7
4 5 8
5 8 2
3 6 3
2 7 4

输出样例 #4

5 1

说明

In the first sample all roads have the same beauty. That means that all paths of the positive length have the same median. Thus, any path with length from $ 3 $ to $ 4 $ , inclusive will be valid for us. In the second sample the city looks like that: 1 - 2 - 3 - 4 - 5 - 6. Two last roads are more valuable and we should choose any path that contains both of them and has the suitable length. It is either the path between $ 2 $ and $ 6 $ or the path between $ 3 $ and $ 6 $ .