24671번 - Kill All Termites 다국어

문제

A tree is an undirected connected graph with $n$ vertices and $n - 1$ edges.

You are given a tree. There are termites in some vertices of this tree. Your task is to kill them all. To do so, you can poison some of the vertices. If a termite visits a poisoned vertex, it immediately dies. Every second, each termite moves to an adjacent vertex. A termite cannot move along the same edge twice in a row, except when it gets into a leaf. Find the minimal possible number of vertices you can poison so that all the termites will eventually die, regardless of their initial positions and strategies.

입력

The first line contains one integer $n,ドル the size of the tree (1ドル \le n \le 100,000円$).

The second line contains $n - 1$ integers $p_2, p_3, \ldots, p_{n},ドル meaning that there is an edge between vertices $i$ and $p_i$ for 2ドル \le i \le n$ (1ドル \le p_i < i$).

출력

Print one integer: the answer.

제한

힌트