Dsa
Trees
Medium
The Social Distance Hierarchy
Given a tree and an integer K, count how many pairs of nodes (u, v) have a distance (number of edges) exactly equal to K.
Input Format:
- Line 1: Two integers N and K.
- Next N-1 lines: u v (an edge).
Output Format:
- A single integer representing the number of pairs.
Example:
Input:
5 2
1 2
2 3
3 4
2 5
Output:
4
(Pairs are: (1,3), (1,5), (3,5), (2,4))
Key concepts
tree dpcombinatorics
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now