Problem Setter: panik
Difficulty: Medium
Prerequisites: DP on Trees, DFS
Explanation:
This is a DP on trees question. In this, we need to optimally traverse the tree by keeping track of different paths using DP as repetition occurs.
we need a DP array of dimension DP[N][K] where K maximum value of J possible and N is no. of nodes. As we need to skip nodes according to the given conditions we would need 2 DFS functions, one to skip J level of nodes(where J is the penalty of that node if selected) and one for normal traversal and DP table filling. To fill the DP we use a top-down approach since the data structure in use is a tree so linear traversal is not possible.
So we start from the tree root, now we have the option of selecting it or not. If we select it then the state of its next selected node would be its current state xor value, and if not selected we would directly go to its children and pass its current state as it is and calculate the max value from them.
Author’s Solution: click here (the code is well commented for your understanding)
Tester’s Solution: click here (using only 1 dfs function by the help of flag variable)