High-quality Tree

The binary search tree is one of the most useful data structures in computer science. Many methods exist to keep them balanced, such as tree rotations (as in AVL trees) or randomness (as in treaps). These methods are all somewhat slow and complicated.

Rob the computer scientist has invented a new method to keep rooted binary trees balanced. It is much better than the current state of the art. The main idea is to repeatedly perform an operation Rob calls a robbery. One robbery takes a leaf from the tree and removes it. By applying robberies at the right times, Rob keeps a tree balanced in $\mathcal{O}(1)$ amortized time.

Some people have criticised Rob's revolutionary discovery, saying that removing elements from the tree makes the algorithm incorrect. Rob does not agree that this is a big problem. If you plan to store $2 \cdot 10^5$ numbers, you probably do not need all of them. Rob accepts the criticism and decides to find a way to minimise the number of robberies.

Figure H.1: Illustration of Sample Input 2. The tree becomes strongly balanced after removing the three vertices marked in red ($4$, $5$, and $10$), which is the minimum number of vertices that need to be removed to make the tree strongly balanced.

You are given a rooted binary tree with $n$ vertices. The vertices are numbered from $1$ to $n$, and vertex $1$ is the root. Your task is to find the minimum number of robberies to make the tree strongly balanced, meaning that all of its subtrees are balanced. A rooted binary tree is balanced if the depths of its left and right subtrees differ by at most one. Recall that a robbery removes a leaf, and doing so may turn its parent into a leaf.

The input consists of:

• One line with an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), the number of vertices in the tree.
• $n-1$ lines, each with two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u\neq v$), an edge between vertices $u$ and $v$.

The given edges form a valid binary tree with vertex $1$ as the root. The edges can appear in any order and are undirected: $u$ may be the parent of $v$, or the other way around.

Output the minimum number of leaves you need to remove to make the tree strongly balanced.