题目描述

给定一个有 $N$个点（编号 0,1,…,$N$−1）的树，每条边都有一个权值（不超过 1000）。

树上两个节点 $x$ 与 $y$之间的路径长度就是路径上各条边的权值之和。

求长度不超过$K$的路径有多少条。

输入格式

输入包含多组测试用例。

每组测试用例的第一行包含两个整数 $N$和$K$。

接下来 $N$−1 行，每行包含三个整数 $u,v,l$，表示节点 $u$与$v$ 之间存在一条边，且边的权值为$l$。

当输入用例 $N$=0，$K$=0 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果。

每个结果占一行。

样例

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

8

数据范围

$1≤N≤10^4, 1≤K≤5×10^6, 0≤l≤10^3$

来源

• POJ1741
• 算法竞赛进阶指南