#PU1020. USACO 2020 February Contest, Platinum — Problem 1. Delegation
USACO 2020 February Contest, Platinum — Problem 1. Delegation
USACO 2020 February Contest, Platinum — Problem 1. Delegation
题目描述
Farmer John's farm consists of pastures () connected by
roads, so that any pasture is reachable from any other pasture. That is,
the farm is a tree. But after 28 years of dealing with the tricky algorithmic
problems that inevitably arise from trees, FJ has decided that a farm in the
shape of a tree is just too complex. He believes that algorithmic problems are
simpler on paths.
Thus, his plan is to partition the set of roads into several paths and delegate
responsibility for these path among his worthy farm hands. He doesn't care about
the number of paths. However, he wants to make sure that these paths are all as
large as possible, so that no farm hand can get away with asymptotically
inefficient algorithms!
Help Farmer John determine the largest positive integer such that the roads
can be partitioned into paths of length at least .
输入格式
The first line contains a single integer .
The next lines each contain two space-separated integers and
describing an edge between vertices and . Both and are in the
range .
输出格式
Print .
数据范围
In test cases 2-4 the tree forms a star; at most one vertex has degree
greater than two.
Test cases 5-8 satisfy .
Test cases 9-15 satisfy no additional constraints..
样例
样例 1
8
1 2
1 3
1 4
4 5
1 6
6 7
7 8
3
One possible set of paths is as follows:
$$2-1-6-7-8, 3-1-4-5$$
Problem credits: Mark Gordon and Dhruv Rohatgi