레이팅 미적용농부 존의 농장은 \(N-1\)개의 도로로 연결된 \(N\)개의 목초지(\(2 \leq N \leq 10^5\))로 이루어져 있으며, 어느 목초지에서든 다른 어느 목초지로도 갈 수 있다. 즉, 농장은 트리이다. 하지만 트리에서 필연적으로 생겨나는 까다로운 알고리즘 문제들을 28년 동안 다뤄 온 농부 존은, 트리 모양의 농장은 너무 복잡하다고 결론지었다. 그는 알고리즘 문제가 경로에서는 더 단순하다고 믿는다.
그래서 그의 계획은 도로 집합을 여러 개의 경로로 분할하고, 이 경로들에 대한 책임을 유능한 일꾼들에게 나눠 위임하는 것이다. 경로의 개수는 상관하지 않는다. 다만, 어떤 일꾼도 점근적으로 비효율적인 알고리즘으로 대충 넘어갈 수 없도록, 이 경로들이 모두 가능한 한 길기를 원한다!
도로들을 길이가 \(K\) 이상인 경로들로 분할할 수 있는 가장 큰 양의 정수 \(K\)를 농부 존이 구하도록 도와주자.
문제 제공: Mark Gordon, Dhruv Rohatgi
배점
- 테스트 케이스 2-4에서 트리는 별(star) 모양이다. 즉, 차수가 2보다 큰 정점이 많아야 하나이다.
- 테스트 케이스 5-8은 \(N\le 10^3\)을 만족한다.
- 테스트 케이스 9-15는 추가 제약이 없다.
문제 제공: Mark Gordon, Dhruv Rohatgi
첫째 줄에 정수 \(N\)이 하나 주어진다.
다음 \(N-1\)개의 줄 각각에 정점 \(a\)와 \(b\) 사이의 간선을 나타내는, 공백으로 구분된 두 정수 \(a\)와 \(b\)가 주어진다. \(a\)와 \(b\)는 모두 \(1 \ldots N\) 범위이다.
\(K\)를 출력한다.
deleg.in · 출력을 쓸 파일 deleg.out8
1 2
1 3
1 4
4 5
1 6
6 7
7 83One possible set of paths is as follows:
$$ 2-1-6-7-8, 3-1-4-5 $$
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > February > Platinum