#PU1020. USACO 2020 February Contest, Platinum — Problem 1. Delegation

    ID: 1166 传统题 文件IO:deleg 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb20来源:usaco.orgscoring:equal_test_cases树上算法

USACO 2020 February Contest, Platinum — Problem 1. Delegation

USACO 2020 February Contest, Platinum — Problem 1. Delegation

题目描述

Farmer John's farm consists of NN pastures (2≤N≤1052 \leq N \leq 10^5) connected by

N−1N-1 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 KK such that the roads

can be partitioned into paths of length at least KK.

输入格式

The first line contains a single integer NN.

The next N−1N-1 lines each contain two space-separated integers aa and bb

describing an edge between vertices aa and bb. Both aa and bb are in the

range 1…N1 \ldots N.

输出格式

Print KK.

数据范围

In test cases 2-4 the tree forms a star; at most one vertex has degree

greater than two.

Test cases 5-8 satisfy N≤103N\le 10^3.

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