루미 알고리즘

#1594플래티넘Trafikverket's Plan

PO 2024 온라인 예선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

During the winter, far too many accidents occur in Lönnköping due to icy roads. Because the municipality of Lönnköping wanted to appear even more efficient than the cat kingdom Katen's conquest (see Segment Monitoring), their road network has very few roads. The N houses only have N-1 roads between them in total. Each road directly connects two houses. If you are at a certain house, you can travel to another house using road connected to the house you are at. The network is also designed such that one can travel between every pair of houses by traversing one or more roads. The traffic department has devised a brilliant plan to reduce the number of accidents: they intend to make each road in the network one-way, so that everyone can commute to work in the morning. In the evening, they will simply reverse all directions so that everyone can return home.

The only problem is that they are unsure whether or not their plan will work. What if some residents cannot get to work in the morning? The traffic department has compiled a list of where each resident lives and works and now wants you to determine, for each resident, whether they can commute to work given their new plan. Their plan consists of the description of the road network and the direction each road should have.

Input

The first line of the input contains the integer N (1 ≤ N ≤ 3 · 10^5), the number of houses in Lönnköping.

The following N-1 lines each contain the integers a,b (1 ≤ a,b ≤ N, a ≠ b), meaning that there is a one-way road from house a to house b. It is guaranteed that the the undirected edges form a tree.

The next line contains the integer Q (1 ≤ Q ≤ 10^5), the number of residents of Lönnköping.

Afterwards, Q lines following, each containing the integers H_i,W_i (1 ≤ H_i,W_i ≤ N), the index of the house where resident i lives and works respectively.

Output

For each resident, print “ja” if they can get to work under the new plan. Otherwise, print “nej”. Print these in the same order of people as in the input.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

GroupPoint valueConstraints
110N, Q ≤ 1000
210W_i=1 for all i.
310∣a-b∣=1 for all pairs of (a,b) such that there exists a road between a and b, that is to say that the tree is a line.
425For all pairs (a,b) such that there exists a road between a and b, it holds that ⌊(max(a,b))/2 ⌋=min(a,b). In other words, the tree is a full binary tree.
515N ≤ 50000
630No additional constraints.

Samples

Sample 3 satisfies the constraints for subtask 3 and sample 4 satisfies the constraints for subtask 4.

예제

예제 1

입력
5
1 2
2 3
4 2
5 1
3
5 2
3 1
4 3
출력
ja
nej
ja

예제 2

입력
10
1 5
2 7
5 2
1 3
3 6
9 6
4 3
2 10
8 2
5
1 2
3 3
1 5
7 10
8 5
출력
ja
ja
ja
nej
nej

예제 3

입력
5
1 2
2 3
3 4
5 4
2
1 4
1 5
출력
ja
nej

예제 4

입력
7
1 2
4 2
5 2
3 1
6 3
3 7
2
7 2
5 5
출력
nej
ja

출처 표기

출처: Programmeringsolympiaden 2024년 온라인 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.