#OJ1454. em 10 树

em 10 树

em 10 树

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

给定一个含有n个节点的树,每个边的长度小于1001。求树上有多少点对的距离小于k。

Input

第一行输入一个数T代表测试数据个数(T<=20)。每个测试样例第一行两个正整数n,k ( 0 < n<=10000)。接下n-1行,每行3个正整数u,v,l代表边(连接u,v点,长度为l)。(1<=u,v<=n)

Output

对于每个输入样例输出树上有多少点对的距离小于k。每行输出一个结果。

Sample Input

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

Sample Output

8

HINT

Append Code

Source