问题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
来源/分类
[提交] [状态]