Skip to content

Latest commit

 

History

History

0252

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

题目

给定一个有 $N$ 个点(编号 $0,1,…,N-1$)的树,每条边都有一个权值(不超过 $1000$)。

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

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

输入格式

输入包含多组测试用例。

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

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

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

输出格式

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

每个结果占一行。

数据范围

$1 \le N \le 10^4$,

$1 \le K \le 5 \times 10^6$,

$0 \le l \le 10^3$

输入样例:

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

输出样例:

8

题解