27924번 - 윤이는 엄청난 것을 훔쳐갔습니다 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 366 | 195 | 161 | 55.326% |
문제
윤이는 엄청난 것을 훔쳐 갔다!
UDP 마을의 경찰인 달구와 포닉스는 윤이를 잡기 위해 출동했다. UDP 마을은 $N$개의 정점을 가진 트리 구조로 되어 있다. 트리는 $N$개의 정점과 $N-1$개의 간선으로 이루어진 연결 그래프이다. 트리에서 이웃한 정점이 하나밖에 없는 정점을 리프 노드라고 부른다.
트리의 각 정점에는 $1$번부터 $N$번까지 번호가 붙어 있다. 윤이는 정점 $a$에서 출발하고, 달구와 포닉스는 각각 정점 $b$, $c$에서 출발한다. 주어지는 세 정점은 서로 다르다. 윤이, 달구, 포닉스는 다음과 같이 번갈아 이동하며 추격전을 벌인다. 이동 도중 한 정점 위에 둘 이상이 존재해도 된다.
- 먼저 윤이가 간선을 따라 이웃한 정점으로 이동한다.
- 그다음 달구와 포닉스가 각각 간선을 따라 이웃한 정점으로 이동한다.
윤이는 경찰과 동일한 정점에 위치하는 즉시 경찰에게 잡힌다. 반면, 윤이가 경찰에게 잡히지 않고 리프 노드에 도달하면 즉시 이웃한 마을로 탈출할 수 있다. 윤이가 리프 노드에서 출발하는 경우도 마찬가지다.
윤이, 달구, 포닉스가 최선의 전략으로 추격전을 벌일 때, 윤이는 무사히 탈출할 수 있을까?
입력
첫 번째 줄에 UDP 마을의 정점 개수 $N$이 주어진다. ($3\le N\le 200\ 000$)
다음 $N-1$개의 줄에 트리의 간선 정보를 나타내는 정수 $u$, $v$가 주어진다. 정점 $u$와 $v$ 사이에 간선이 존재함을 나타낸다. ($1\le u,v\le N$)
그다음 줄에 윤이, 달구, 포닉스의 위치를 나타내는 정수 $a$, $b$, $c$가 주어진다. ($1\le a,b,c\le N$; $a$, $b$, $c$는 서로 다르다.)
출력
윤이가 탈출할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.
예제 입력 1
8 1 2 2 3 3 4 4 5 5 6 2 7 4 8 3 1 6
예제 출력 1
YES
예제 입력 2
8 1 2 2 3 3 4 4 5 5 6 2 7 5 8 3 1 6
예제 출력 2
NO
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호