A8434. Freezing with Style
编程题
普及/提高-
知识点
题目描述
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.
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}$ .
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$ .
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$ .