Question
n nodes are there in a tree with values ranging from 0 to n-1. Each node has got some cost (either +ve or -ve). Complete the function to calculate the maximum cost to reach n-1th node from 0th node. You can skip at most 2 consecutive nodes in the path (cannot skip 0th or n-1th node). Total no of skips is not constrained.
4 Input parameters are given
1st -> n (no of nodes in the given tree): type = integer
2nd -> q_from (starting node of the edge): type = array of size n-1
3rd -> q_to (ending node of the edge): type = array of size n-1
4th -> w (weights of each node): type = array of size n
Test case 0
Input :
n = 4
q_from = [0, 1, 2]
q_to = [1, 2, 3]
w = [10, -10, -20, 30]
Ans = 40 ( 0 -> 3 ) by skipping nodes 1 and 2
0 (10)
/
1 (-10)
/
2 (-20)
/
3 (30)Test case 1
Input :
n = 5
q_from = [0, 1, 2, 2]
q_to = [1, 2, 3, 4]
w = [10, -10, -20, 30, 40]
Explanation:
Edges are 0-1, 1-2, 2-3, 2-4. Left node belongs to q_from and right node belongs to q_to
Possible paths are -
0 -> 1 -> 2 -> 4 Cost = 20
0 -> 1 -> 4 Cost = 40
0 -> 2 -> 4 Cost = 30
0 -> 4 Cost = 50
Maximum of all paths is ( 0 -> 4 ) with cost of 50
Ans = 50 ( 0 -> 4 ) by skipping nodes 1 and 2
0 (10)
/
1 (-10)
/
2 (-20)
/ \
3 (30) 4 (40)Test case 2
Input :
n = 5
q_from = [0, 1, 2, 2]
q_to = [1, 2, 3, 4]
w = [10, 1, -20, 30, 40]
Ans = 51 ( 0 -> 1 -> 4 ) by skipping nodes 2
0 (10)
/
1 (1)
/
2 (-20)
/ \
3 (30) 4 (40)Complete the given function to return the max cost:
def maxCostPath(n, q_from, q_to, w):
Comments (7)