#2521. 树上两点之间的路径数

树上两点之间的路径数

Description

一棵有nn 个节点的树,每条边都有一个 长度(小于10011001的正整数),dist(u,v)dist(u , v )为节点uuvv 的最小距离。 给定一个整数kk ,对每对节点(u,v)(u , v ),当且仅当dist(u,v)dist(u , v )不超过 kk 时才叫作有效。计算给定的树中有多少对节点是有效的。

Format

Input

输入包含几个测试用例。每个测试用例的第1行都包含两个 整数nkn10000n 、k (n ≤10000),下面的n1n -1行,每行都包含三个整数uvlu 、v 、l ,表示节点uu vv 之间有一条长度为ll 的边。在最后一个测试用例 后面跟着两个00

Output

对每个测试用例,都单行输出答案。

Samples

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

来源

POJ1741