Tom’s Area Tom is a male cat. He doesn’t like when someone enters his area while he is sleeping. Tom has a habit of sleep walking. His master, Neko, wants to enter his room without disturbing and entering Tom’s possible sleeping area. Tom covers a radius of r units. Help Neko in figuring out what all possible areas he cannot enter. Given n, r, and list of edges, find and print the number of different areas Neko cannot enter. The area of path selected cannot be isomorphic. Input: The first line contains two space-separated integers, n and r. Each of the next n-1 lines contains two separated integers a and b (which is a bidirectional edge) with a unit length. Output: Print, a single integer, the total number of areas. Constraints: 1<= n <=3000 0<= r <=3000 1<= x, y <=n Sample Test Case: Sample Input: 7 1 1 5 2 7 1 2 1 3 1 4 2 6 Sample Output: 3 Explanation: In the diagram below, blue nodes denote the possible areas Tom can sleep in: The last 5 areas are considered to be the same (i.e., they all consist of two nodes connected by one edge), so we print 3 as our answer.
Tom’s Area
Tom is a male cat. He doesn’t like when someone enters his area while he is sleeping. Tom has a habit of sleep walking. His master, Neko, wants to enter his room without disturbing and entering Tom’s possible sleeping area. Tom covers a radius of r units. Help Neko in figuring out what all possible areas he cannot enter.
Given n, r, and list of edges, find and print the number of different areas Neko cannot enter. The area of path selected cannot be isomorphic.
Input:
The first line contains two space-separated integers, n and r.
Each of the next n-1 lines contains two separated integers a and b (which is a bidirectional edge) with a unit length.
Output:
Print, a single integer, the total number of areas.
Constraints:
1<= n <=3000
0<= r <=3000
1<= x, y <=n
Sample Test Case:
Sample Input:
7 1
1 5
2 7
1 2
1 3
1 4
2 6
Sample Output:
3
Explanation:
In the diagram below, blue nodes denote the possible areas Tom can sleep in:
The last 5 areas are considered to be the same (i.e., they all consist of two nodes connected by one edge), so we print 3 as our answer.
Step by step
Solved in 3 steps with 2 images