BZPRO

#2812. 世界树

内存限制：512 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述


世界之树，又称“乾坤树”。在北欧神话中，巨大的树干构成了整个世界。
                                                                                                 ——百度百科
世界树由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程序有误，请不要提交!

BZPRO Powered by XZYQvQ.
Github Repository