This page is still under construction.

Parts of this page are still being built. What you see may change.

Hidden Supervisors

Time limit3sMemory limit512 MB

Summary
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 11.

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 nn, the number of employees (2≤n≤100 0002 \le n \le 100\,000).

The second line contains n−1n - 1 integers p2,p3,…,pnp_2, p_3, \dots, p_n (0≤pi≤n0 \le p_i \le n), where pip_i is the supervisor reported by employee ii. If employee ii did not reply, pip_i is 00. The Big boss has number 11.

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.

Examples2

  1. Example 1

    Input
    6
    3 1 0 4 4
    
    Expected output
    2
    
  2. Example 2

    Input
    6
    3 1 0 6 4
    
    Expected output
    3