Mocha and his friend wants to go on a vacation trip but they live in different cities. There are total of n cities given in form a binary tree rooted at vertex 1. To meet each other Mocha and his friend always stat travelling from their city towards the root.
For travelling each city they need to fill their fuel tank and you are given the cost required to fill the tank at each vertex. You need to fill the tank each city you visit. Mocha and his friend travel until they meet for the first time at same vertex/city.
You will be given binary tree rooted at vertex 1 and an array 'cost' (1-based indexing) which contains the cost of fuel required to fill at each vertex i.e. cost to refill the fuel at ith vertex is cost[i] (1 <= i <=n).
You will be asked q queries which contains the start cities of Mocha(x) and his friend(y).
All cities have a unique rule that once they sell their fuel then next time they need to reduce the cost to half of current cost (floor value should be considered).
You need to find the money Mocha and his friend together spent on all of their trips in each city i.e. Money spent on each vertex after all the queries.
Input : cost = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], root = 1 2 3 4 5 6 7 8 null null null null null 9 10 , queries = [ [4, 7], [8, 10], [4, 5], [6, 7], [2, 3] ]
Output : [1, 3, 4, 7, 5, 6, 11, 8, 0, 10]
Explanation :
1st query -> traverse from vertex 4 to 7 and they meet at common vertex 1 for first time. The path is 4 -> 2-> 1 -> 3 -> 7.
2nd query -> traverse from vertex 8 to 10 and they meet at common vertex 1 for first time. The path is 8 -> 4 -> 2 -> 1 -> 3 -> 7 -> 10.
3rd query -> traverse from vertex 4 to 5 and they meet at common vertex 2 for first time. The path is 4 -> 2-> 5.
4th query -> traverse from vertex 6 to 7 and they meet at common vertex 3 for first time. The path is 7-> 3-> 6.
5th query -> traverse from vertex 2 to 3 and they meet at common vertex 1 for first time. The path is 2-> 1 -> 3.
So vertex 7 is traversed in query 1, 2, 4. So initial cost is 7 for tank refill. So after traversal in 1st query the cost is halved i.e. becomes 7/2 -> 3.5 -> 3.
After traversal in 2nd query cost is halved again 3/2 -> 1.5 -> 1.
After traversal in 4th query cost is halved again 1/2 -> 0.5 -> 0.
So total money spent by Mocha and his friend on 7th vertex/city after all the queries is 7 + 3 + 1 => 11.
Input : cost = [3, 5, 4, 6], root = 1 3 2 4 , queries = [ [2, 3] ]
Output : [3, 5, 4, 0]
Explanation :
1st query traversal path => 2 -> 1 -> 3.
Cost at vertex1 -> 3.
Cost at vertex 2 -> 5.
Cost at vertex 3 -> 4.
Cost at vertex 4 -> 0.
Input : cost = [10, 6, 6, 6, 10, 10], root = [1, 2, 4, 3, 5, null, null, 6], queries = [ [3, 5], [2, 6] ]