루미 알고리즘

#1606플래티넘Reseplaneraren

PO 2025 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

After using public transport for several years, you have noticed that Bästtrafik's route planning app is not very good. It often suggests routes with 3 transfers, when you know that the journey can be made without any transfers at all! To demonstrate how incompetent they are, you will develop a competing app that determines if it is possible to travel from station A to station B without any transfers.

The public transport network in Gothenburg can be described by its N stations. These stations are connected by several roads. The network of roads is designed so that it is possible to travel between every pair of stations, and it contains exactly N-1 roads. This means that the road network forms a tree. In a tree, a path is defined as a sequence of stations where each station is directly connected to the next in the sequence, and no station is visited more than once. The path between two stations is always the shortest and the only possible path connecting them. The public transport consists of K tram lines running through the network. Each tram line has a tram that travels between two stations, start and end. This tram travels back and forth between the start and end stations repeatedly. The roads have enough tracks to ensure that trams never get stuck or end up in a traffic jam.

Your app must now answer Q questions of the form: "Can you travel from station a to station b without transfers?" In other words, can you board a tram at station a, let the tram ride for a while, and then get off at station b? To mock Besttrafik as much as possible, you don't care at all about how long the journey takes.

Input

The first line of input contains the integers N, K, and Q (1 ≤ N, K, Q ≤ 3 · 10^5), the number of stations, tram lines, and questions.

The following N-1 lines each contain two integers u,v (1 ≤ u,v ≤ N, u ≠ v), which means that there is a road between station u and station v.

Next, K lines follow, each containing two integers s,t (1 ≤ s,t ≤ N, s ≠ t), which means that there is a tram line between stations s and t.

The final Q lines each contain two integers a,b (1 ≤ a,b ≤ N, a ≠ b), representing a question of whether you can travel from station a to station b without transfers.

Note that this problem has a very large input size. Therefore, it is recommended to use fast input reading.

Output

For each question, print “Yes” if it is possible to make the journey without transfers, otherwise print “No”. Print these in the same order as the questions.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
17N, K, Q ≤ 100
219N, K, Q ≤ 1000.
313N, K, Q ≤ 5 · 10^4
423For each query, a is on the path between 1 and b.
538No additional constraints.

Explanation of Sample 1

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Visualization of Sample 1. The black edges represent the roads, and the colored areas represent each tram line.

  • Question 1: It is not possible to travel from station 1 to station 3 without a transfer. If transferring once were allowed, it would have been possible.
  • Question 2: There isn't even a tram line going to station 4, so it is certainly not possible to make the journey without transfers.
  • Question 3: Here, we can take the tram line between stations 1 and 2.
  • Question 4: Here, we can take the tram line between stations 5 and 3.

예제

예제 1

입력
5 2 4
1 2
2 3
3 4
3 5
1 2
2 5
1 3
4 3
1 2
5 3
출력
No
No
Yes
Yes

출처 표기

출처: Programmeringsolympiaden 2025년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.