Algorithm - Count Paths in Range

$1.$ Find centroid $c$ using the standard algorithm.

$2.$ DFS from $c$ to get all distances.

For each distance $d$, count distances in range $[k_1 - d, k_2 - d]$ using a data structure that supports range queries.

$3.$ Subtract pairs where both nodes are in the same child subtree using the same range-counting approach.

$4.$ Recurse on components after removing $c$.

Use a sorted list or balanced tree to count range matches efficiently in $O(\log n)$ per query.

Space complexity is $O(n)$ for the data structures used.