2019 Fall KBTU OPEN
Kill all termites
There are termites on the tree. Your task is to kill them all. The tree is an undirected connected graph with n vertices and n - 1 edges. In order to kill termites you are able to poison some vertices. If the termite hits the vertex with poison, then he immediately dies. You don’t know where termites are located initially. But you know that termites go to the random adjacent vertex each time, but if termite has passed edge (u, v), next edge should be different from (v, u), except the case, when termite hits the leaf (in this case, termite turns around and goes back). You need to poison minimum number of vertices, such that termites hits poisoned vertices after finite number of steps.
On the first line you are given single integer n (1 ≤ n ≤ 100000). On the next line you are given n - 1 integers
pi (2 ≤ i ≤ n), so there is an edge connecting
pi and i.
On the single line output single integer - minimum number of poisoned vertices.
8 1 1 2 1 2 3 2