题目描述

Tar 国正在准备每年一次的巡游活动。国王将会在一个城市 $S$ 里召集人群，沿着城市间的道路进行游览，最终在一个城市 $T$ 里发表他每年一次的著名演讲。

Tar 国有 $n$ 个城市，由于国家的特殊要求，每两个城市之间存在一条唯一的简单通路。

国王希望借着这个机会视察 Tar 国的城市建设，因此他提出 $S$ 到 $T$ 的距离不能少于 $l$ 条道路。

同时，国王的私人医生检查了他的身体情况后，断定国王的身体不适合做长途旅行，因此他要求 $S$ 到 $T$ 的距离不能多于 $r$ 条道路。

另外，政府希望跟随国王的人民沿途不仅能看到城市风景，还能看到城市外的美丽乡村。因此每条道路定义了一个魅力值 $c_i$，一条路径的魅力值定义为这条路径的中位数。

更详细的说法是这样的：

将路径上所有边的魅力值排序，得到序列 ${a_i}$。假设 $i=2k+c\ (0 \leq c \leq 1)$，中位数就是 $a_{k+1}$。

你的任务就是求出魅力值最大的路径，并输出这个魅力值。

输入格式

第一行是三个整数 $n,l,r$，表示 Tar 国的城市个数、路径的最小和最大长度。

接下来 $n-1$ 行，每行三个整数 $a_i,b_i,c_i$，表示有一条连接 $a_i$ 和 $b_i$ 且魅力值 $c_i$ 的道路。

输出格式

仅一行，表示最大的魅力值。如果不存在这样的路径，输出 $-1$。

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

7

数据规模与约定

• 对于 $100\%$ 的数据：$n \leq 10^5$，$1 \leq l \leq r \leq n-1$，$1 \leq c_i \leq 10^9$。

题目来源

树的分治