题目描述

现在给你一棵共有$n$个节点的树。树上每条边有黑色和白色两种颜色。

显然，树上任意不同的两点$u, v$之间有一条简单路径。记为$d(u, v)$。称这条路径是好的，当且仅当这条路径至少满足下列条件之一：

• 路径上颜色全部相同。
• 路径上黑色边的总量不大于$k$。

你的任务是求解共有多少条好路径。其中，$d(u, v)$和$d(v, u)$视为同一条路径。

输入格式

第一行两个整数$n$和$k$，含义同题面描述。

接下来$n-1$行，每行三个整数$u, v, c$，表示$u$和$v$之间有一条连边，当$c=1$时为黑边；$c=0$时为白边。

输出格式

一行一个整数，表示答案。

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

8

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

9

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

7

数据规模与约定

每组数据点10分，共10组数据。

大样例

大样例下载