题目描述

给定一棵 $n$ 个点的无根树，边有权值，求有多少条路径，使得路径长度不超过 $k$。

输入格式

第一行一个正整数 $n$，表示树的结点数。 接下来 $n-1$ 行每行三个整数 $u,v,w$，表示 $u,v$ 之间存在一条长度为 $w$ 的无向边。 接下来一行一个整数 $k$，如题意所示、

输出格式

一行一个整数表示答案。

7
1 6 13 
6 3 9 
3 5 7 
4 1 3 
2 4 20 
4 7 2 
10

5

数据范围

$1\le n\le 1\times 10^5$，$k$ 和所有边权之和在 int 范围内。

题目来源

LTC男人八题系列