×

# Editorial for MISSME - PELT2019

 0 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) asked 11 Jan, 18:20 5★panik 116●6 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,556
×693
×50
×10
×6
×2