Last Updated: 21 Feb, 2021
Tree Jumping
Hard
Asked in company
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.
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.
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.
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
Approaches
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.
The idea is to first create an adjacency list and then use depth-first search or breadth-first search same as the previous approach in order to create an array of vectors ‘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 use another depth-first search to compute the maximum number of special nodes that can be reached using the following dp state.
dp[current_node][K] = max( max{ dp[child_i][K], for all children of current_node },
max{ dp[node_at_same_height_i][K - 1],
for all nodes at same height as current_node} )
Here, K is the number of horizontal jumps remaining.
Algorithm
- 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 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.
- Create a matrix dp[][] of size N*K, where ‘N’ is the number of nodes and ‘K’ is the maximum number of horizontal jumps allowed. initially fill it with -1.
- 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 a number of horizontal jumps remain. In each recursive call perform the following operations.
- If dp[curr][k] != -1, return dp[curr][k].
- 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 the 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.
- Assign dp[curr][K] = ‘maxScore’.
- Return ‘dp[curr][K]’.
- The value returned by this recursive function call will be the answer.