Find centroid using the standard algorithm.
DFS from to get all distances.
For each distance , count distances in range using a data structure that supports range queries.
Subtract pairs where both nodes are in the same child subtree using the same range-counting approach.
Recurse on components after removing .
Use a sorted list or balanced tree to count range matches efficiently in per query.
Space complexity is for the data structures used.