← 返回题目列表

Codeforces · 150/E

E. 风格冻结

中文机器翻译题面 查看原题

这个冬天是如此......好吧,你已经明白了:-) Nvodsk 道路系统可以表示为与 n - 1 条双向道路连接的 n 个交叉路口,因此任意两个交叉路口之间都有一条路径。一些活动的组织者想要选择一个容纳参与者的地方(v 路口),以及举办比赛的地方(u 路口)。此外,一方面,他们希望参与者在城市中漫步并看看邻居(这就是为什么 v 和 u 之间的距离应该不小于 l)。另一方面,他们不希望参与者冻结(因此 v 和 u 之间的距离不应大于 r)。此外,对于每条街道,我们都知道它的美丽程度 - 0 到 109 之间的某个整数。您的任务是选择符合长度限制且具有最大平均美丽程度的路径。我们将平均美丽度定义为沿途所有道路的美丽度序列的中位数。

我们可以更正式地说:设一条长度为k的路径。令 ai 为恰好包含 k 个元素的非递减序列。每个数字出现的次数恰好是路径上出现如此美丽的道路的次数。我们将路径中位数表示为数字 a⌊k / 2⌋,假设使用从零开始的索引。 ⌊x⌋ — 是数字 х,向下舍入到最接近的整数。

例如,如果 a = {0, 5, 12},则中位数等于 5,如果 a = {0, 5, 7, 12},则中位数为数字 7。

保证至少有一条具有适当数量道路的路径。

输入

第一行包含三个整数 n、l、r (1 ≤ l ≤ r < n ≤ 105)。

接下来 n - 1 行包含 Nvodsk 道路的描述,每行包含三个整数 ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109, ai ≠ bi) — 交叉点 ai 和 bi 与一条美丽等于 ci 的街道相连。

输出

打印两个整数 - 路口的数量,相应地容纳参与者并设置比赛。如果有多个最佳变体,请打印其中任何一个。

示例

输入 #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

注意

在第一个示例中,所有道路都具有相同的美感。这意味着所有正长度的路径具有相同的中值。因此,任何长度从 3 到 4(含 3 和 4)的路径对我们来说都是有效的。

在第二个样本中,城市看起来像这样:1 - 2 - 3 - 4 - 5 - 6。最后两条路更有价值,我们应该选择包含这两条路且长度合适的任何路径。它要么是 2 到 6 之间的路径,要么是 3 到 6 之间的路径。