P5969 [POI 2016] Nadajniki

Byte Town has $n$ houses, numbered from $1$ to $n$. These houses are connected by $n-1$ undirected roads, forming a tree. Bytesear wants to deploy a WiFi network in Byte Town, and he wants WiFi to cover every road in the town. Bytesear can place an unlimited number of WiFi transmitters, but they can only be placed on nodes of the tree. A house can have multiple WiFi transmitters. For a road $(a,b)$, if it satisfies at least one of the following two conditions, then this edge is considered covered by WiFi: - A WiFi transmitter is placed at node $a$ or node $b$. - Among the nodes directly adjacent to node $a$ or node $b$, at least two WiFi transmitters are placed in total. Please help Bytesear find an optimal placement plan so that WiFi covers every road in Byte Town, while the total number of WiFi transmitters used is as small as possible.

The first line contains a positive integer $n$, the total number of houses. The next $n-1$ lines each contain two positive integers $a, b$, indicating that there is an edge between nodes $a$ and $b$.

Output one integer in a single line: the minimum total number of WiFi transmitters.

For $100\%$ of the testdata, $2\le n\le2 \times 10^5$, $1\le a,b\le n$. ---- ### Sample Explanation: Place two WiFi transmitters at node $3$. Translated by ChatGPT 5