A very very hard problem (need help)

Revision en1, by User0069, 2023-06-28 18:55:46

Giving an undirected weighted graph of n (n <= 1e5) vertices , n — 1 edges and an positive integer k (k <= 1e9). Count the number of pairs (i , j) that i < j and the weight of the path from i to j is not bigger than k.

Input the first line contain n and k the following n — 1 lines each contains three positive integer u , v , w (u , v <= n , w <= 1e9)

Output the number of pairs (i , j) that the weight of the path from i to j is not bigger than k.

Sample

INPUT 6 8 1 2 2 2 3 4 2 5 1 4 5 3 5 6 5

OUTPUT 14

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English User0069 2023-06-29 06:47:42 20
en1 English User0069 2023-06-28 18:55:46 582 Initial revision (published)