Tree Modification
Contest: Codeforces Global Round 9
Difficulty rating: 2800
Tags: brute force, constructive algorithms, dfs and similar, graph matchings, graphs, trees

You are given a tree with $$$n$$$ vertices. You are allowed to modify the structure of the tree through the following multi-step operation:

1. Choose three vertices $$$a$$$, $$$b$$$, and $$$c$$$ such that $$$b$$$ is adjacent to both $$$a$$$ and $$$c$$$.
2. For every vertex $$$d$$$ other than $$$b$$$ that is adjacent to $$$a$$$, remove the edge connecting $$$d$$$ and $$$a$$$ and add the edge connecting $$$d$$$ and $$$c$$$.
3. Delete the edge connecting $$$a$$$ and $$$b$$$ and add the edge connecting $$$a$$$ and $$$c$$$.

As an example, consider the following tree:

The following diagram illustrates the sequence of steps that happen when we apply an operation to vertices $$$2$$$, $$$4$$$, and $$$5$$$:

It can be proven that after each operation, the resulting graph is still a tree.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree $$$n - 1$$$, called its center, and $$$n - 1$$$ vertices of degree $$$1$$$.

Input format:
The first line contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$)  — the number of vertices in the tree.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) denoting that there exists an edge connecting vertices $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the given edges form a tree.

Output format:
Print a single integer  — the minimum number of operations needed to transform the tree into a star.

It can be proven that under the given constraints, it is always possible to transform the tree into a star using at most $$$10^{18}$$$ operations.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first test case corresponds to the tree shown in the statement. As we have seen before, we can transform the tree into a star with center at vertex $$$5$$$ by applying a single operation to vertices $$$2$$$, $$$4$$$, and $$$5$$$.

In the second test case, the given tree is already a star with the center at vertex $$$4$$$, so no operations have to be performed.

Example input:
6
4 5
2 6
3 2
1 2
2 4

Example output:
1

Example input:
4
2 4
4 1
3 4

Example output:
0

Editorial:
The solution is based on the following observation: Every tree is a bipartite graph, i. e. its vertices can be colored black or white in such a way that every white vertex is adjacent only to black vertices and vice versa. Notice that a tree is a star if and only if one of the colors appears exactly once.
Let's fix a bipartite coloring of the tree and look at what happens when we apply the operation to vertices $$$a$$$, $$$b$$$, and $$$c$$$. For concreteness, let's suppose that $$$b$$$ is black, so $$$a$$$ and $$$c$$$ must be white. When we perform the operation:
• Every neighbor of $$$a$$$ other than $$$b$$$ is black. After connecting it to $$$c$$$ it remains black since $$$c$$$ is white.
• After connecting $$$a$$$ to $$$c$$$ it must switch from being white to being black since $$$c$$$ is white.
• Every other vertex is unaffected by the operation.
Thus every operation changes the color of exactly one vertex! Suppose that initially there are $$$b$$$ black vertices and $$$w$$$ white vertices. Then we need at least $$$\min(w, b) - 1$$$ operations to turn the tree into a star since one of the colors must end up having a single vertex. This is always achievable: as long as there are at least two vertices with a certain color we can choose two which are adjacent to a common neighbor and use the operation to recolor one of them.
The values of $$$w$$$ and $$$b$$$ can be found through a simple DFS, leading to an $$$O(n)$$$ solution.