Problem 4842. -- Poj1741 Tree

4842: Poj1741 Tree

Time Limit: 1 Sec  Memory Limit: 30 MB
Submit: 18  Solved: 13
[Submit][Status][Web Board]

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001). 
Define dist(u,v)=The min distance between node u and v. 
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. 
Write a program that will count how many pairs which are valid for a given tree. 

给定一个带权树N个结点(1<=N<=10000),定义dist(u,v)为u,v两个点间的最 
短路径长度,路径长度定义为路径上所有边的权和。再给定一个K(1<=K<=10^9) 
如果对于不同的两个结点a,b.如果满足dist(a,b)<=K,则称其为合法点对,求 
有多少合法点对

Input

The input contains several test cases. 
The first line of each test case contains two integers n, k. (n<=10000) 
The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. 
The last test case is followed by two zeros. 

Output

For each test case output the answer on a single line. 

Sample Input

5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0

Sample Output

8

HINT

Source

[Submit][Status]