Tree Jumping

Hard
0/120
Average time to solve is 50m
profile
Contributed by
1 upvote
Asked in company
D.E.Shaw

Problem statement

There is a tree with ‘N’ nodes, numbered from 0 to ‘N-1’. Node 0 is the root of the tree.

Initially, you are at the root node and start jumping on the tree. You can make two kinds of jumps. The first one is the Vertical jump and the second one is the Horizontal jump.

In Vertical jump, you can jump from a node to any of its child nodes (i.e the node that is directly connected to the current node by an edge, and its height from the root is 1 more than the current node).

In Horizontal jump, You can jump from a node to any node at the same level (i.e. the height of nodes from the root are the same). You cannot jump from node to itself.

You can make any number of Vertical jumps, but you can make at most ‘K’ Horizontal jumps.

Some nodes in this tree are special, whenever you reach a special node your score increments by 1. Initial your score is 0.

You are given an integer array ‘Special’ of size ‘N’, where ‘Special[i]’ is 1 if the ith node is special, otherwise ‘Special[i]’ is 0. You are also given an array ‘Edges’ of size ‘N-1’ representing edges of the given tree. Find out the maximum score you can achieve if you start from the root and can make at most ‘K’ horizontal jumps and any number of vertical jumps. Your score increments by 1 as soon as you reach the special node. Your journey will be completed when you can’t make any further jump and the score achieved till that point will be your final score.

For example, consider the following tree having 12 nodes and let ‘K’ = 2. Special nodes are colored red.

alt text

The maximum number of fruits you can collect is 7 if you can make at most 2 horizontal jumps. One such way of climbing this tree is shown in the figure below. The curved line denotes jumps.

alt text

Your score increases by 1 when you reach at node 1, 4. 6, 7, 8, 10, 11 in this tree.

Note:

1. You can visit the same node more than once and each time when you reach a special node your score will be increased by 1.
2. You cannot make a jump from node to itself.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases are as follows -: 

The first line contains two space-separated integers ‘N’, ‘K’ representing the number of nodes and the maximum number of horizontal jumps respectively.

The second line contains ‘N’ space-separated integers 0 or 1, representing the elements of array ‘special’.

Each of the next ‘N’-1 lines contains 2 space-separated integers ‘U’ and ‘V’, that represent there is an undirected edge between node ‘U’ and node ‘V’.

Output Format:

For each test case, print the maximum score you can achieve if you start jumping on a tree from root and can make at most ‘K’ horizontal jumps and any possible number of vertical jumps.

The output of each test case will be printed in a new line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 100
0 <= K <= 10
0 <= Special[i] <= 1
0 <= U, V < N
It is guaranteed that the given edges form a tree, also there will be no self loops and multiple edges.

Where ‘T’ is the number of test cases,  ‘N’, ‘K’ representing the number of nodes and the maximum number of horizontal jumps respectively, and ‘Special[i]’ represents whether the ith node is special or not.


Time Limit: 1 sec
Sample Input 1:
2
1 1
1
4 0
0 0 1 0
0 1
0 2
0 3
Sample Output 1:
1
1
Explanation of the Sample Input1:
Test case 1:
There is only one node in the tree, and this node (root node) is a special node. As in starting you are at the root node, so your score increment by ‘1’. You cannot make any jump further.

Test case 2:
Here, k = 0, so you cannot make any horizontal jump. The best strategy is to make one vertical jump to node 2. This will increment your score by 1. You cannot make any further jump from here.
Sample Input 2:
1
12 2
0 1 0 1 1 0 1 1 1 0 1 1
0 1
0 2
1 3
1 4
2 6
6 5
6 7
4 8
8 9
8 10
10 11
Sample Output 2:
7
Explanation of the Sample Input 2:
Test case 1:
See the problem statement for an explanation.
Hint

Try out all possible ways to make jumps on the tree.

Approaches (2)
Brute Force

The idea is to first create an adjacency list and then use depth-first search or breadth-first search to create a 2D array ‘level’ where ‘level[i]’ is the list of all nodes present at height ‘i’, and an array ‘parent’ such that parent[i] gives the parent of the ith node. Then we will find out the maximum score recursively as follow -:

 

Algorithm

  • This is a recursive approach.
  • Create an adjacency list ‘adj’ of the given tree.
  • Create an array of vectors ‘level’ of size ‘N’. ‘level[i]’ will store all nodes whose height from the root node (node 0) is ‘i’.  The height of each node can be found easily using the depth-first search or breadth-first search.
  • Create an array ‘parents’ of size ‘N’. ‘parent[i]’ will store the parent of node ‘i’. The parent node of each node can also be found using the depth-first search or breadth-first search.
  • Recursively try out all possible ways to make jumps on the trees and find out the maximum score that can be achieved. To do this we make a recursive function, let's name it ‘treeJumpHelper(curr, height, K)’ and call this function with (0, 0, K), Here ‘curr’ is the current root, ‘height’ is the distance of current root from node 0, ‘K’ is the number of horizontal jumps remains. In each recursive call perform the following operations.
    • Initialize an integer variable ‘maxScore’:= 0.
    • First try all possible ways of making the vertical jump, in vertical jump ‘height’ increased by 1. We can do this by Iterating over all the children of the ‘curr’ and for each child call ‘treeJumpHelper(childNode, height+1, k)’ and update ‘maxScore’ with a maximum of its current value and value returned by each recursive call. Note, children will be all the nodes adjacent to a given node except its parent.
    • Try out all possible ways of making a horizontal jump, in horizontal jump ‘height’ will remain the same, but the balance of the horizontal jump will decrease by 1.  We can do this by Iterating over each of the nodes which is at the same height (other than ‘curr’) as of ‘curr’ and for each such node call ‘treeJumpHelper(node, height, ‘K-1)’ and update ‘maxScore’ with a maximum of its current value and value returned by each recursive call.
    • If the node ‘curr’ is a special node, then increment ‘maxScore’ by  1.
    • Return ‘maxScore’.
  • The value returned by this recursive function call will be the answer.
Time Complexity

O(N^N), where ‘N’ is the number of nodes in the tree.

 

Recursion depth can go up to ‘N’ and at each level of the recursion, we can make at most ‘N’ calls. Thus, the time complexity will be O(N^N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the tree.

 

Recursion depth can go up to ‘N’. Thus, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Tree Jumping
Full screen
Console