Кількість маршрутів#11651
Є міст, які пронумеровані числами від до . Міста сполучені N - 1 дорогами з двостороннім рухом. Відомо, що між будь-якими двома містами існує шлях напряму, або такий, що проходить через інші міста. На проїзд однієї дороги між парою міст витрачається одиниця пального. На кожній дорозі є заправна станція, яка дозволяє здійснити заправку на певну кількість одиниць пального.
Машина рухається з міста в місто найкоротшим маршрутом, тобто шляхом, що має найменшу кількість доріг. Відомо, що машина здійснює заправку всього один раз (на одній із доріг маршруту) на тій заправній станції, яка забезпечить заправку на максимальну кількість одиниць пального.
Знайдіть кількість пар міст (, ), для яких в результаті переїзду з міста у місто різниця між придбаним на заправній станції пальним та витраченим на переїзд буде не меншою за задане число .
У першому рядку записані два натуральних числа: та (1 \leq N, K \leq 100000).
Далі слідують N - 1 рядків, у кожному з яких наведено інформацію про дороги, що сполучають міста X_i та Y_i та кількість одиниць пального на заправній станції C_i у формі трьох цілих чисел: X_i, Y_i та C_i(1 \leq X_i, Y_i \leq N, 1 \leq i \leq N - 1, 1 \leq C_i \leq 100000).
Одне ціле число – кількість пар міст (, ), для яких в результаті переїзду з міста у місто різниця між придбаним на заправній станції пальним та витраченим на переїзд не буде меншою за задане число .
При цьому пари міст (, ) та (, ) вважаються різними.
Example 1
