Codeforces Global Round 9 |
---|
Finished |
You are given a tree with $$$n$$$ vertices. You are allowed to modify the structure of the tree through the following multi-step operation:
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$$$.
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.
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.
6 4 5 2 6 3 2 1 2 2 4
1
4 2 4 4 1 3 4
0
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.
Name |
---|