Kill All Termites

시간 제한1초메모리 제한256 MB

요약

나무를 어느 정점에서 뿌리내리고, 같은 간선을 연속으로 되짚지 않고 걷는 흰개미가 언제나 독점에 닿도록 독을 바를 최소 정점 수를 구한다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
1
```
예상 출력
```
1
```
예제 2
입력
```
2
1
```
예상 출력
```
1
```
예제 3
입력
```
8
1 1 2 1 2 3 2
```
예상 출력
```
2
```