| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 45 | 19 | 18 | 58.065% |
A country has $N$ cities numbered from 1ドル$ to $N$ and $N - 1$ bidirectional highways. It is possible to travel from any city to any other city using only the highways.
The distance between two cities $x$ and $y$ is defined as the number of highways required to travel from $x$ to $y$.
The governor has decided to demolish a highway and build another highway such that the largest distance between any two cities is maximized.
Find this maximum largest distance.
Your Program must read from standard input.
The first line contains an integer, $N,ドル the number of cities.
In the next $N - 1$ lines, each line contains 2ドル$ distinct integers $u$ and $v,ドル representing a highway connecting cities $u$ and $v$.
Your program must print to standard output.
The output should contain a single integer on a single line, the new largest distance between any two cities.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N ≤ 10$ |
| 2 | 10 | $N ≤ 100$ |
| 3 | 15 | $N ≤ 3000$ |
| 4 | 15 | $N ≤ 300,000円,ドル there is at most one city with at least 3 highways connected to it. |
| 5 | 55 | - |
4 1 2 1 3 3 4
3
It is impossible to increase the largest distance beyond 3.
This testcase is valid for all subtasks.
6 1 2 2 3 2 5 4 5 5 6
5
We may remove highway 2-5, and add the highway 3-4, so that the longest path becomes 1 − 2 − 3 − 4 − 5 − 6.
This testcase is valid for subtasks 1, 2, 3 and 5.
Olympiad > National Olympiad in Informatics (Singapore) > Qualification > NOI 2022 Qualification 2번