世界树

时间限制:20s      空间限制:512MB

题目描述


世界之树,又称“乾坤树”。在北欧神话中,巨大的树干构成了整个世界。
                                                                                                 ——百度百科
世界树由n个节点构成,共有n-1条枝干连接,任意两个节点都可以互相到达。这一天,主神奥丁准备视察一些树上的种族(比如精灵族,神族,海族,兽族,不死族,还有人族)。但是奥丁只想视察树上的一条路径(不能重复地经过某条枝干),由于他的某种特殊爱好,他还要求路径长度不超过R,且不低于L。已知每条枝干都有一个美丽度,奥丁希望自己视察的路径的美丽度的平均值尽可能地大。
路径美丽度的平均值定义为:将路径上所有枝干的美丽度从小到大排序后,第Trunc(Len/2)+1个美丽度,len指这一条路径的长度。
请你告诉奥丁,他的路径应该从哪个节点出发,到哪个节点结束。


输入格式

第一行三个整数:n,L,R
接下来n-1行:
每行三个整数:x, y, z
代表一条连接x节点和y节点的枝干,美丽度为z


输出格式

输出两个节点u,v,表示从u出发,v结束美丽度最大。
如果有多组答案,任意输出一组。


样例输入

10  2  5
2  1  0
3  2  10
4  2  5
5  3  1
6  4  5
7  3  10
8  6  10
9  6  12
10  5  0

样例输出

8 9

提示


【数据规模及约定】
对于30%的数据保证:n <= 1000
对于100%的数据保证:n <= 100000,1 <= L <= R <= n-1,1 <= x,y <= n,
0 <= z < 2^31,数据保证有解。
请尽量优化常数。

SPJ程序有误,请不要提交!


题目来源

没有写明来源

Menuappsclose