P4178 Tree

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$.

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 a single integer on one line, the answer.

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