Counting Pairs within Distance in a Tree

Problem Statement:

Given a tree with \(n\) nodes and weighted edges, count the number of pairs of nodes whose distance is at most \(k\). The distance between two nodes is defined as the sum of the weights on the unique path connecting them.

Input Constraints:

• The first line contains two integers: \(n\) (the number of nodes) and \(k\) (the maximum allowed distance).
• The next \(n-1\) lines each contain three integers \(u\), \(v\), and \(w\), which describe an edge between nodes \(u\) and \(v\) with weight \(w\). It is guaranteed that the given graph is a tree and nodes are numbered from 1 to \(n\).

Output:

Output a single integer that represents the number of unordered pairs of nodes \((i, j)\) with \(i < j\) such that the distance between \(i\) and \(j\) is less than or equal to \(k\).

inputFormat

Input Format:

• The first line contains two integers \(n\) and \(k\).
• Each of the following \(n-1\) lines contains three integers \(u, v, w\) which denote an edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

Output Format:

• Output a single integer: the number of pairs \((i, j)\) with \(i < j\) and the distance between \(i\) and \(j\) is at most \(k\).

sample

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

8