5회 문제풀이 09 / ABC 209 D - Collision
ABC 209 D - Collision
【문제 개요】
타카하시왕국은 N개의 마을과 N - 1개의 도로로 이루어져 있어, 마을에는 1부터 N까지의 번호가 붙어 있습니다.
또, i(1 ≤ i ≤ N-1)번째 도로는 마을 aᵢ과 bᵢ를 쌍방향으로 연결되어 있어, 모든 도시는 도로를 통해 서로 연결되어 있습니다. 도로는 모두 같은 길이입니다
당신은 다음과 같은 질문을 Q번 받게 됩니다. i(1 ≤ i ≤ P)번째의 질문으로 정수 cᵢ, dᵢ가 주어집니다. 이하의 문제를 해결하시오.
- 현재 타카하시군은 마을 cᵢ에서, 아오키군은 마을 dᵢ에 있습니다. 두사람이 동시에 마을을 출발하여 각각 마을 dᵢ, cᵢ를 목표로 같은 속도로 이동할 때, 두사람이 마을에서 만날지 도로위에서 만날지 판단하시오. 단, 두사람 모두 최단 경로로 이동하며, 마을의 안에서 이동하는 시간은 무시하여도 좋다.
힌트 : 그래프 이론과 최단 경로 알고리즘
그래프가 트리 구조이므로 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)로 각 도시의 깊이를 계산
【전제】
- 2 ≤ N ≤ 10⁵
- 1 ≤ P ≤ 10⁵
- 1 ≤ aᵢ < bᵢ ≤ N(1 ≤ i ≤ N-1)
- 1 ≤ cᵢ < dᵢ ≤ N(1 ≤ i ≤ P)
- 입력은 모두 정수이다.
- 어떤 마을에서 다른 마을로 여러 도로를 통하는것으로 이동 가능하다.
【입력 형태】
1
2
3
4
5
6
7
8
9
N Q
a₁ b₁
a₂ b₂
...
aₙ₋₁ bₙ₋₁
c₁ d₁
c₂ d₂
...
cₚ dₚ
【출력 형태】
Q개의 행으로 각 질문에 대한 대답을 출력하시오. i행의(1 ≤ i ≤ P)째로 i번째의 질문에 대해서 두사람이 마을에서 만난다면 Town, 도로에서 만난다면 Road라고 출력하시오.
【예시】
입력 예 1
1
2
3
4
5
4 1
1 2
2 3
2 4
1 2
출력 예 1
1
Road
1번째의 질문에는 타카하시군은 마을1, 아오키군은 마을2에서 동시에 출발하여 1번째의 도로위에서 만납니다. 따라서 Road라고 출력하세요.
입력 예 2
1
2
3
4
5
6
7
5 2
1 2
2 3
3 4
4 5
1 3
1 5
출력 예 2
1
2
Town
Town
1번째의 질문에는 타카하시군은 마을1, 아오키군은 마을3에서 동시에 출발하여 마을2에서 만납니다. 따라서 Town이라고 출력하세요. 2번째의 질문에는 타카하시군은 마을1, 아오키군은 마을5에서 동시에 출발하여 마을3에서 만납니다. 따라서 Town이라고 출력하세요.
입력 예 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
9 9
2 3
5 6
4 8
8 9
4 5
3 4
1 9
3 7
7 9
2 5
2 6
4 6
2 4
5 8
7 8
3 6
5 6
출력 예 3
1
2
3
4
5
6
7
8
9
Town
Road
Town
Town
Town
Town
Road
Road
Road
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。