COCI 2020/2021 - Contest 4 - Janjetina

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.5s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 4
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Sau khi nhà hàng trên toàn Croatia phải đóng cửa vì phong tỏa, Malnar ban đầu cảm thấy rất buồn bã. Sau đó, anh ấy sớm nhận ra không có việc gì phải buồn nữa và quyết định sau khi các nhà hàng mở cửa trở lại, anh ấy sẽ đi khắp Croatia và đãi anh ấy món thịt cừu ngon nhất của các nhà hàng Croatia.

Malnar muốn thăm ~n~ thành phố, được đánh số từ ~1~ đến ~n~. Các thành phố này có ~n-1~ đường hai chiều nối chúng, đảm bảo có thể di chuyển giữa hai cặp thành phố bất kì.

Trên mỗi con đường, có một nhà hàng bán thịt cừu, và Malnar biết khối lượng thịt cừu anh ấy có thể đặt ở mỗi nhà hàng.

Anh ấy sẽ chọn hai thành phố phân biệt ~x~ và ~y~, và di chuyển từ ~x~ đến ~y~ bằng đường đi ngắn nhất (đường đi đi qua ít con đường nhất). Anh ấy sẽ dừng lại ở đúng một nhà hàng, nơi mà anh ấy có thể đặt nhiều thịt cừu nhất (nếu tồn tại nhiều nhà hàng, anh ấy sẽ chọn một nhà hàng bất kì) và anh ấy sẽ ăn tất cả khối lượng thịt cừu mà anh ấy đặt.

Malnar cho rằng con đường có độ dài ~l~ mà anh ấy ăn ~w~ kilogram thịt cừu là thỏa mãn nếu ~w - l \geq k~. Độ dài của một con đường là số đường đi nó đi qua.

Anh ấy muốn biết số cặp thành phố phân biệt ~(x,y)~ mà đường đi ngắn nhất từ ~x~ đến ~y~ là thỏa mãn. Anh ấy rất bận nên anh ấy đã nhờ bạn tính kết quả cho anh ấy.

Input

Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \leq n, k \leq 100\:000)~, lần lượt là số lượng thành phố và ngưỡng thỏa mãn.

Mỗi dòng trong ~n-1~ dòng tiếp theo gồm ~3~ số nguyên ~x, y~ và ~w~ ~(1 \leq x, y \leq n, \: x \neq y, \: 1 \leq w \leq 100\:000)~, thể hiện một con đường nối ~x~ và ~y~ và có một nhà hàng trên đó mà Malnar có thể đặt ~w~ kilogram thịt cừu.

Output

In ra số cặp thành phố phân biệt ~(x,y)~, sao cho mà đường đi ngắn nhất từ ~x~ đến ~y~ là thỏa mãn.

Sample 1

Input
3 1
1 2 3
1 3 2
Output
6

Sample 2

Input
4 1
1 2 1
2 3 2
3 4 3
Output
6

Sample 3

Input
5 2
1 2 2
1 3 3
3 4 2
3 5 4
Output
8
Giải thích

Các cặp thỏa mãn là ~(1, 3), (3, 1), (1, 5), (5, 1), (3, 5), (5, 3), (4, 5)~ và ~(5, 4)~.

Subtask

  • 22 test đầu có ~N \leq 1000~.
  • 18 test sau thỏa thành phố thứ ~i~ ~(1 \leq i \leq n-1)~ và ~i+1~ có đường nối trực tiếp.
  • 26 test còn lại không có ràng buộc gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.