Description

Given a tree with $n$ nodes where each edge has a weight, find the number of pairs of nodes whose distance on the tree is less than or equal to $k$.

Input Format

The first line contains an integer $n$, the number of nodes.

Lines $2$ to $n$ each contain three integers $u, v, w$, indicating there is an edge between $u$ and $v$ with weight $w$.

Line $n+1$ contains an integer $k$.

Output Format

Output a single integer on one line, the answer.

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

5

Hint

Constraints

For all test points, it is guaranteed that:

• $1 \le n \le 4 \times 10^4$.
• $1 \le u, v \le n$.
• $0 \le w \le 10^3$.
• $0 \le k \le 2 \times 10^4$.

Translated by ChatGPT 5