P5258 [JSOI2013] Confusion During Travel

Waldives has $N$ small islands. The current transportation system contains $N-1$ express boat routes, and each express boat route connects two islands. These $N-1$ express boat routes form a tree. For special reasons, all $N-1$ express boat routes are one-way. This makes many pairs of islands unable to reach each other. Therefore, the Waldives government wants to build some new bus routes so that after construction, any two islands can reach each other. To save money, the government wants to build as few bus routes as possible. At the same time, for planning reasons, each bus route must satisfy the following requirements: > 1. Each transportation route contains several consecutive express boat routes. You may treat one bus route as a path on the tree, and the express boat routes it contains correspond to the tree edges covered by this path (that is, some express boat routes that already exist). > > 2. Obviously, a transportation route can cover any edge on the tree at most once. > > 3. Each express boat route included in a bus route has a direction, and this direction is opposite to the direction of the tree edge it covers. > > 4. Different bus routes may cover the same vertices or the same edges on the tree. The $N$ islands of Waldives are numbered from $0$ to $N-1$. Now the existing express boat route information of Waldives is given. Please compute the minimum number of new transportation routes that need to be built.

The first line contains an integer $N$. The next $N-1$ lines each contain two integers $x,~y$, meaning that there is an express boat route from island $x$ to island $y$.

Output one line with one integer, representing the minimum number of transportation routes that need to be built.

$1~\leq~N~\leq~10^5$ Translated by ChatGPT 5