레이팅 미적용농부 존의 농장은 \(N-1\)개의 도로로 연결된 \(N\)개의 목초지(\(2 \leq N \leq 10^5\))로 이루어져 있으며, 어느 목초지에서든 다른 어느 목초지로도 갈 수 있다. 즉, 농장은 트리이다. 하지만 트리에서 필연적으로 생겨나는 까다로운 알고리즘 문제들을 28년 동안 다뤄 온 농부 존은, 트리 모양의 농장은 너무 복잡하다고 결론지었다. 그는 알고리즘 문제가 경로에서는 더 단순하다고 믿는다.
그래서 그의 계획은 도로 집합을 여러 개의 경로로 분할하고, 각 경로에 대한 책임을 유능한 일꾼에게 위임하는 것이다. 다툼을 피하기 위해, 그는 각 경로의 길이가 모두 같기를 원한다. 그는 어떤 길이에 대해 그러한 분할이 존재하는지 궁금하다.
더 정확히는, 각 \(1 \leq K \leq N-1\)에 대해 도로들을 길이가 정확히 \(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\) 범위이다.
길이 \(N-1\)의 비트 문자열을 출력한다. 각 \(1\le K\le N-1\)에 대해, 이 문자열의 왼쪽에서 \(K\)번째 비트는 트리의 간선들을 길이가 정확히 \(K\)인 경로들로 분할할 수 있으면 1, 그렇지 않으면 \(0\)이어야 한다.
deleg.in · 출력을 쓸 파일 deleg.out13
1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13111000000000It is possible to partition this tree into paths of length \(K\) for \(K=1,2,3.\)
For \(K=3\), a possible set of paths is as follows:
$$ 13-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1 $$
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > February > Gold