题目描述

给定一个有 $N$ 个点（编号 $0,1,\dots,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

样例解释

$N=5, K=4$

树的边：

• 0-1 权值 3
• 0-2 权值 1
• 0-3 权值 2
• 2-4 权值 1

树结构：

   0
 / | \
1  2  3
   |
   4

计算所有长度不超过 4 的路径（包括单个点？不，路径至少两个点吧？通常路径定义为两个不同点之间的简单路径，但这里可能包括单点？需要明确。一般树上的路径是指两个节点之间的简单路径，且两点不同）。

计算所有点对间距离：

• (0,1)：3 ≤ 4
• (0,2)：1 ≤ 4
• (0,3)：2 ≤ 4
• (0,4)：2 ≤ 4
• (1,2)：4 ≤ 4
• (1,3)：5 > 4
• (1,4)：5 > 4
• (2,3)：3 ≤ 4
• (2,4)：1 ≤ 4
• (3,4)：4 ≤ 4

符合条件的点对有 9 个？但输出是 8。

可能 (0,0) 不算路径？路径必须两个不同点。
那么符合条件的点对恰好 8 个（排除 (1,3) 和 (1,4)）。

数据范围

• $1 \le N \le 10^4$
• $1 \le K \le 5 \times 10^6$
• $0 \le l \le 10^3$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB