Minimum Supply Stations

You are given a tree representing a network of cities connected by roads. There are n cities, numbered from 1 to n, and the network is given as a set of n - 1 roads, where each road connects two different cities. Your task is to determine the minimum number of supply stations that need to be built so that every city either has a supply station or is directly connected to a city with a supply station.

Formally, if you designate a set S ⊆ {1, 2, ..., n} as the cities where supply stations are built, for every city there must exist a city i ∈ S such that either the city is i or there is a road connecting the city to i. The goal is to minimize |S|. This can be formulated using the following DP recurrence with a tree structure:

\[ \text{dp}[v][1] = 1 + \sum_{u \in \text{children}(v)} \min(\text{dp}[u][0], \text{dp}[u][1]) \] \[ \text{dp}[v][0] = \sum_{u \in \text{children}(v)} \text{dp}[u][1] \]

Note: For a single city (n = 1), the answer is 1.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of cities.
• The next n - 1 lines each contain two integers u and v (1 ≤ u, v ≤ n), indicating that there is a road connecting city u and city v. For the case when n=1, no additional lines are provided.

outputFormat

Output a single integer to standard output (stdout) which represents the minimum number of supply stations required to cover all cities.

1

1