Hidden Supervisors
Time limit3sMemory limit512 MB
Given a partial parent array, fill in the missing supervisors to complete a rooted tree and maximize the number of disjoint parent-child pairs.
- Level
Hard8 of 10
- Topics
- Tree, Dynamic programming, Greedy, DFS
- Solved
- No attempts yet
Problem
Helena works as a psychologist in a large company. Her current job is to organize a team building game that improves relations between employees. Every employee except the Big boss has exactly one supervisor, so the employees form a tree. Each employee is a node, and the parent of a node is that employee's supervisor. The root of the tree is the Big boss, whose number is .
A team in this game has two people, an employee and that employee's supervisor. Each person joins at most one team.
Helena asked every employee except the Big boss to send the number of their supervisor, and some of them did not reply. She will assign a fake supervisor to every employee who did not reply. The real and fake supervisors together must still form a tree rooted at the Big boss.
Find the largest number of teams she can arrange.
Input
The first line contains one integer , the number of employees ().
The second line contains integers (), where is the supervisor reported by employee . If employee did not reply, is . The Big boss has number .
At least one way exists to assign a fake supervisor to every employee who did not reply so that all employees form a tree rooted at the Big boss.
Output
Print the maximum number of teams on one line. Do not print the supervisor assignment itself.