P2996 [USACO10NOV] Visiting Cows G

After many weeks of hard work, Bessie is finally getting a vacation. She wants to visit $N$ friends, labeled $1,2 \dots, N$. The cows have set up an unusual road network with exactly $N - 1$ roads connecting pairs of cows $C_1$ and $C_2$ ($1 \le C_1 \le N$, $1 \le C_2 \le N$, $C_1 \ne C_2$), so that there is a unique path between any two cows. FJ wants Bessie to come back to the farm soon; therefore, if two cows are directly connected by a road, she may not visit both. Bessie would like her vacation to be as long as possible, so she wants to determine the maximum number of cows she can visit. Constraints: $1 \le N \le 50000$.

* Line 1: A single integer $N$. * Lines 2..$N$: Each line describes one road with two space-separated integers: $C_1$ and $C_2$.

* Line 1: A single integer representing the maximum number of cows that Bessie can visit.

Bessie knows $7$ cows. The roads form the following tree: ```plain 1--2--3--4 | 5--6--7 ``` Bessie can visit four cows. The best combinations include two cows on the top row and two on the bottom. She cannot visit cow 6 since that would prevent visiting cows 5 and 7; thus she visits 5 and 7. She can also visit two cows on the top row: $\{1, 3\}$, $\{1, 4\}$, or $\{2, 4\}$.