开心消消乐

题号：NC212881
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

YanGu有一个 n 个点的树,即由 n-1条边连接起来的联通图,每条边都有颜色 $w_i$ . 定义 path(u,v) 为 u 到 v 的简单路径,不妨设有 m 条边,颜色按 u 到 v 的路径顺序排列分别为 $w_1,w_2 \dots w_m$ , 且有 p 个连续的颜色段,相邻的颜色段颜色不同,颜色分别为 $d_1,d_2 \dots, d_p$ , 长度分别为 $l_1,l_2 \dots, l_p$ , 显然有 $\sum_{i=1}^{p} {l_i} = m$ . 对于颜色段定义
$power(d,l)=\left\{ \begin{aligned} 0 & & {l \geq 3} \\ d \times l & & {else} \end{aligned} \right.$
其中 d 为颜色, l 为长度.
定义
$value (u,v) = \frac{\sum_{i=1}^{p} power(d_i,l_i)}{\sum_{i=1}^{p}{l_i}}$
譬如 u 到 v 按顺序经过的路径颜色为 1,2,2,2,3,4,4,4,4,4,3,3,1, 则此时 $value(u,v) = \frac{1 + 3 + 3 + 3 + 1}{13}$ , 因为存在连续 3 个颜色 2 和连续 5个颜色 4 消为0.
YanGu想知道有多少个这样的二元组 (u,v) 满足 $value(u,v) \geq k$ .

输入描述:

第一行含有一个整数 T 表示测试数据组数. 对于每组测试数据,
第一行含有两个整数 n, k 表示点的个数和阈值, 
接下来 n-1行,每行
有三个整数 u,v,w 表示 u 和 v 之间边的颜色为 w

* 
* 
* 
* 
* 
* 
* 至多有50组

输出描述:

对于每个测试数据 , 输出一个整数表示答案

示例1

输入

复制

2
5 4
1 2 3
1 3 5
2 4 5
3 5 4
8 50809177
1 2 700805901
2 3 32145015
3 4 792263333
3 5 538420696
1 6 351870424
2 7 263716407
5 8 818097140

输出

复制

9
27