← 返回题目列表

AtCoder · njpc2017_e

E. 边缘村庄

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

配点 : 700 点

問題文

由罗夫君是深山边缘村庄的村长。这个边缘村庄的每条路都有一个由村规民约确定的“吉祥方向”。如果违反村规矩,逆着吉祥方向行驶,就会遭到村民的冷眼。边缘村是 N 土地并将土地与土地连接起来 N-1 由一条主干道组成,该地块为 它的编号为 1,2,...,N 。i 番目 (1 ≦ i ≦ N-1) 道路就是土地 A_i 和 按字典顺序比较 B_i ,而那条路的吉祥方向是陆地。 A_i 减去 B_i 方向。土地 在 A_i 和 按字典顺序比较 B_i 之间移动 需要 C_i 分钟。当将其视为以土地为顶点、以道路为边的无向图时,该无向图是连通的。有关人们从一个地方到达另一个地方必须走的所有道路的信息。 C 的求和需要时间。

由罗夫君正试图在一个边缘村庄选择土地建造一所学校。我们希望避免出现一些学生需要很长时间才能到达学校的情况,所以我们不想避免一些学生需要很长时间才能到达学校的情况。 D 我想在几分钟内就能到达学校的地方建一所学校。此外,为了避免学生在上学途中受到村民冷眼的注视,部分道路的吉祥方向需要改变。我们希望在一块土地上建造一所学校,既满足上学时间限制,又尽量减少需要改变交通吉利方向的道路数量。求当学校建在这样的土地上时,交通方向发生吉祥变化的次数。如果没有满足就学时间限制的土地,则输出-1。 不存在

制約

  • 所有输入均为整数
  • 2 ≦ N ≦ 10^5
  • 1 ≦ A_i, B_i ≦ N
  • A_i ≠ B_i
  • i ≠ j, A_i = A_j, B_i = B_j 这样的东西
  • i ≠ j, A_i = B_j, A_j = B_i 这样的东西
  • 0 ≦ C_i ≦ 10^3
  • 1 ≦ D ≦ 10^9
  • 如果你无视村规,你可以通过多条道路从任何一块土地到达任何一块土地。

入力

输入是按以下格式从标准输入给出的。

N D
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{N-1} B_{N-1} C_{N-1}

出力

在一块满足上学时间限制且村规民约变更次数最少的土地上建学校时,输出村规民约变更次数。如果没有满足就学时间限制的土地,则输出-1。


入力例 1

7 15
2 1 2
3 2 3
2 4 5
4 5 1
4 6 4
7 6 6

出力例 1

2

能够满足就学时间限制的土地为 2、4、5 和 6。这些土地满足限制的村规必须更改的最少次数分别为 4、3、2 和 2。