Magical Tree Curse

Problem Statement

Magical Tree Curse Problem Description Alex has found a magical tree with n nodes labelled 1 to n , joined by n - 1 branches. No node touches more than 3 branches, and the root, node 1 , touches at most 2 . The root is cursed from the start. The forest then runs through phases. In each phase Alex may remove one node that is neither cursed nor already removed, together with its branches, or may do nothing. After the phase, the curse spreads from every cursed node to every node still joined to it. A node is saved if it is never cursed. Removed nodes do not count as saved. Report the largest number of nodes Alex can save. Input Format Line 1: the integer n . The next n - 1 lines: two integers u v , a branch between nodes u and v . Output Format One integer: the maximum number of saved nodes. Examples Example 1 Input: 4 1 2 2 3 2 4 Output: 2 Removing node 2 in the first phase cuts the curse off at the root. Nodes 3 and 4 are then joined to nothing cursed and survive. Example 2 Input: 5 1 2