TR-O1. Yaqin qo‘shnilar

Tog‘li tumanda n ta qishloq n − 1 ta so‘qmoq bilan daraxt shaklida ulangan, j-so‘qmoq uzunligi wⱼ metr. Ikki qishloq yaqin hisoblanadi, agar ular orasidagi (yagona yo‘l bo‘yicha) masofa K metrdan oshmasa.

Nechta (tartibsiz) qishloq juftligi yaqin?

Kirish ma’lumotlari

Birinchi qatorda n va K. Keyingi n − 1 qatorda u v w.

Chiqish ma’lumotlari

Bitta son — yaqin juftliklar soni.

Cheklovlar

1 ≤ n ≤ 5·10⁴; 1 ≤ w ≤ 10⁴; 0 ≤ K ≤ 10⁹.

1-misol: masofalar (1, 2) — 3, (1, 3) — 4, (1, 4) — 9, (2, 3) — 7, (2, 4) — 6, (3, 4) — 13. K = 6 dan oshmaydiganlar — 3 ta.