Trees: Depth First Search
Chasing a butterfly
On clear summer days, Nyusha loves to catch butterflies in the fresh air. Today she came across a cunning butterfly: she flew into the labyrinth and wanted to hide in it from Nyusha.
The labyrinth consists of n rooms, numbered from 1 to n, some of which are connected by corridors. It is known that between any two rooms there is a single path from the corridors. In other words, the maze is a tree, and the number of corridors is n - 1.
The entrance to the labyrinth is located in the room number 1. We will call a leaf any room of the labyrinth that is connected by a corridor to exactly one other room and does not coincide with the root. In each of the leaves there is an exit from the labyrinth. The butterfly flies from the entrance towards one of the leaves. It flies at a constant speed and does not turn around. All corridors have the same length, and in one minute the butterfly flies through one corridor, moving to the next room.
To catch the butterfly, Nyusha decided to call a few of her friends. Initially, each of the friends can be located in any of the rooms containing the exit. At the moment when the butterfly starts to fly from the entrance to the labyrinth to one of the exits, each of the friends can start moving from their room towards the entrance. Friends move at the same speed as a butterfly. If one of the friends was at the same point (in the room or in the middle of one of the corridors) with a butterfly, then the butterfly is considered to be caught. If the butterfly reaches the top with the exit, without meeting any of the friends along the way, it will safely flutter out of the maze and fly away to freedom.
Help Nyusha determine the minimum number of friends she needs to be sure to catch the butterfly, no matter which exit it flies to.
The first line contains an integer n (2 ≤ n ≤ 200000) - the number of rooms in the maze.
The next n - 1 lines contain descriptions of the corridors connecting the rooms. Each of these lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) - numbers of rooms connected by the corridor. It is guaranteed that the corridor structure is a tree.
Print one integer - the minimum number of friends needed to be sure to catch a butterfly.
3 1 2 1 3
4 1 2 2 3 2 4