Optimal WiFi Transmitter Placement in Bit Town

In Bit Town there are (n) houses numbered from (1) to (n), connected by (n-1) undirected roads forming a tree structure. Bytesear wants to install WiFi transmitters to cover every road in town. You can install an unlimited number of WiFi transmitters, but only on the houses (nodes) of the tree (a house can have more than one transmitter). An edge ((a, b)) (i.e. a road connecting house (a) and house (b)) is considered covered if at least one of the following conditions holds:

• House \(a\) or house \(b\) has at least one transmitter installed.
• Among the houses directly adjacent to either \(a\) or \(b\), there are at least two transmitters installed (note that a house with two transmitters contributes \(2\) to the count).

It turns out that covering an edge by placing a transmitter on one of its endpoints (thus satisfying the first condition) always costs only (1) and is never more expensive than trying to cover it indirectly using the second condition (which would cost at least (2)).

Therefore, the problem reduces to selecting a set of houses on which to install transmitters such that every road is incident to at least one house with a transmitter. This is equivalent to finding a minimum vertex cover on a tree.

Given the tree structure, a standard tree dynamic programming (DP) solution can be used. For each house (node) (u), let (dp[u][0]) be the minimum cost when (u) is not chosen (in which case all of its children in the DFS tree must be chosen) and (dp[u][1]) be the minimum cost when (u) is chosen. The answer is (\min(dp[1][0], dp[1][1])) when the root is taken as house (1).

inputFormat

The first line contains an integer (n) ((2 \le n \le 10^5)), the number of houses. Each of the following (n-1) lines contains two integers (u) and (v) ((1 \le u, v \le n)), indicating an undirected road connecting house (u) and house (v).

outputFormat

Output a single integer, the minimum number of WiFi transmitters required to cover every road in Bit Town.

sample

2
1 2

1