CF150E Freezing with Style

今年冬天实在是……你懂的 :-) Nvodsk 的道路系统可以表示为 $n$ 个路口，通过 $n-1$ 条双向道路连接，使得任意两个路口之间都存在一条路径。某项活动的组织者希望选择一个地方安置参赛者（路口 $v$），以及一个地方举办比赛（路口 $u$）。一方面，他们希望参赛者在城市里多走动，感受周边环境（因此 $v$ 与 $u$ 之间的距离不少于 $l$）；另一方面，又不希望参赛者太冷（所以 $v$ 与 $u$ 之间的距离不超过 $r$）。此外，每条道路的美丽值都已知，是一个从 $0$ 到 $10^{9}$ 的整数。你的任务是选择一条路径，使得其长度满足限制，并且路径上所有道路美丽值的平均美丽最大。我们定义“平均美丽”为该路径上所有道路美丽值的中位数。 更正式地说：设有一条长度为 $k$ 的路径，记 $a_{i}$ 为一个非递减的序列，包含路径上的每条道路的美丽值，各个美丽值出现的次数等于路径上该美丽值道路的数量。我们用 $a_{\lfloor k/2\rfloor}$ 表示这条路径的中位数（序号从 $0$ 开始）。$\lfloor x\rfloor$ 表示向下取整。 例如，如果 $a={0,5,12}$，则中位数为 $5$；如果 $a={0,5,7,12}$，则中位数为 $7$。 保证至少存在一条长度满足要求的路径。

第一行包含三个整数 $n$、$l$ 和 $r$（$1\le l \le r, n\le 10^{5}$）。 接下来的 $n-1$ 行描述 Nvodsk 所有道路，每行三个整数 $a_{i}$、$b_{i}$、$c_{i}$（$1\le a_{i},b_{i}\le n$，$0\le c_{i} \le 10^{9}$，$a_{i} \ne b_{i}$），表示路口 $a_{i}$ 与 $b_{i}$ 之间有一条美丽值为 $c_{i}$ 的道路连接。

输出两个整数，表示安置参赛者和举办比赛的两个路口编号。如果有多个最优方案，输出任意一组均可。

在第一个样例中，所有道路的美丽值都一样，所以任意正长度路径的中位数都相同。因此，任取一条长度在 $3$ 到 $4$ 之间（包含 $3$ 和 $4$）的路径即可。 在第二个样例中，城市结构如下：1 - 2 - 3 - 4 - 5 - 6。最后两条道路的美丽值更高，因此我们应该选择包含这两条道路且长度合适的任意路径。比如从 $2$ 到 $6$ 或从 $3$ 到 $6$ 的路径。 由 ChatGPT 5 翻译