33493번 - 애벌레와 트리 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 157 | 8 | 4 | 5.714% |
문제
$N$개의 정점으로 이루어진 트리가 있다. 트리의 각 정점은 $1$번부터 $N$번까지 번호가 매겨져 있고, $i$번째 간선은 $u_i$번 정점과 $v_i$번 정점을 연결한다. 이 트리 위에는 애벌레가 한 마리 살고 있는데, 초기 상태에서 애벌레의 머리는 $h$번 정점에 위치해 있고, 애벌레의 꼬리는 $t$번 정점에 위치해 있다. 애벌레는 머리가 위치한 정점과 꼬리가 위치한 정점, 그리고 그 두 정점 간의 경로에 속한 모든 정점을 차지한다.
현재 애벌레의 머리가 $a$번 정점에, 꼬리가 $b$번 정점에 위치해 있다면, 애벌레는 다음의 조건들을 모두 만족하는 $a'$와 $b'$에 대해 머리와 꼬리를 각각 $a'$번 정점과 $b'$번 정점으로 동시에 이동시킬 수 있다.
- $a$번 정점과 $a'$번 정점은 인접해 있고, $b$번 정점과 $b'$번 정점은 인접해 있다.
- $a'$번 정점과 $b'$번 정점 중 정확히 하나는 이동 전 애벌레가 차지하지 않았던 정점이고, 나머지 하나는 이동 전 애벌레가 차지했던 정점이다.
이렇게 이동하더라도 애벌레가 차지하는 정점의 개수는 변하지 않음에 유의하라.
이때 아래와 같은 쿼리 $Q$개에 대해 답해보자.
- $h'$ $t'$: 머리와 꼬리가 각각 $h$번 정점과 $t$번 정점에 위치한 초기 상태의 애벌레가 $0$번 이상의 이동을 통해 머리와 꼬리가 각각 $h'$번 정점과 $t'$번 정점에 위치하게끔 할 수 있는가?
입력
첫 번째 줄에 세 개의 정수 $N$, $h$, $t$가 공백으로 구분되어 주어진다.
다음 $N-1$개의 줄 중 $i$번째 줄에 두 개의 정수 $u_i$, $v_i$가 공백으로 구분되어 주어진다.
다음 줄에 정수 $Q$가 주어진다.
다음 $Q$개의 줄에 쿼리들의 정보가 주어지며, 각 줄에는 두 정수 $h'$와 $t'$가 공백으로 구분되어 주어진다.
출력
$Q$개의 줄에 걸쳐 문제의 정답을 출력한다. $i$번째 줄에는 $i$번째 쿼리의 답이 참이라면 YES를, 거짓이라면 NO를 출력한다.
제한
- $2\leq N\leq 100000$
- $1\leq Q\leq 50000$
- $1\leq u_i,v_i \leq N$
- $u_i\ne v_i$
- $1\leq h,t \leq N$
- $h\ne t$
- $1\leq h',t' \leq N$
- $h'$와 $t'$ 사이의 거리와 $h$와 $t$ 사이의 거리는 같음
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N \leq 300$ |
| 2 | 10 | $N \leq 2000$ |
| 3 | 85 | 추가 제약 조건 없음 |
예제 입력 1
5 3 4 1 2 1 3 1 4 4 5 4 1 5 2 4 2 3 4 2
예제 출력 1
YES YES NO NO
출처
School > 한국과학영재학교 > 2025 KSA Automata Winter Contest J번
- 문제를 만든 사람: edward3378
- 문제를 검수한 사람: ai4youej, flakepowders, hjroh0315, kwoncycle, mythofys, parkky, raehwan0418, utilforever
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호