Company: DevRev
Difficulty: medium
Magical Tree Curse Problem Description In the enchanted forest, Alex has discovered a magical tree with n nodes, labeled from 1 to n. This tree is a connected, acyclic graph with n-1 branches. Each node has a maximum of 3 connections, except the root (node 1), which has up to 2 connections. Unfortunately, the root node is cursed. Over n phases, Alex can: Choose a non-cursed and non-removed node and remove it along with its connections, or Do nothing. After each phase, the curse spreads to all nodes directly connected to already cursed nodes. Alex's goal is to maximize the number of nodes that remain uncursed (removed nodes are not counted as saved). Help Alex determine the maximum number of nodes he can save from the curse. Examples Example 1: Input: 4 1 2 2 3 2 4 Output: 2 Explanation: If we delete vertex 2 we can save vertices 3 and 4. Constraints Execution time limit: 4 seconds (py3) Memory limit: 1 GB Input: integer n Number of vertices in the tree. 2 ≤ n ≤ 3 * 10^5 Input: ar