问题1561--树上多少对节点距离少于给定值(pku 1741)

1561: 树上多少对节点距离少于给定值(pku 1741)

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

给一个有n个顶点的树,每个边都有一个长度(正整数小于1001)。
define dist(u,v)=节点u和v之间的最小距离。
给一个整数k,对于每对顶点(u,v),当且仅当dist(u,v)不超过k时,才称为有效。
编写一个程序,计算对给定树有效的对的数目。

输入

输入包含几个测试用例。每个测试用例的第一行包含两个整数n,k.(n<=10000),下面的n-1行每个包含三个整数u,v,l,这意味着在长度为l_的节点u和v之间有一条边。
最后一个测试用例后面跟着两个零。

输出

对于每个测试用例,将答案输出到一行。

样例输入

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

样例输出

8

来源/分类


[提交] [状态]