P30078

Tree

难度 7 级 树的点分治 图论
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给出一棵有 n 个顶点的树,每条边都有长度(正整数,小于 1001)。

定义 \text{dist}(u, v) 为节点 u 与 v 之间的最小距离。

给定整数 k,对于每对顶点 (u, v) 称为有效,当且仅当 \text{dist}(u, v) \le k。

编写一个程序,计算给定树中有效对数。

输入

输入包含多个测试用例。每个测试用例的第一行包含两个整数 n, k(n \le 10000)。

接下来的 n-1 行,每行包含三个整数 u, v, l,表示节点 u 和 v 之间存在一条长度为 l 的边。

最后一个测试用例后面跟两个零。

输出

每个测试用例输出一行答案。

样例

样例 1
输入
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
输出
8
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交