시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 226 | 111 | 83 | 45.856% |
한국항공대학교는 $n$ 개의 건물로 이루어져 있으며, 두 건물을 잇는 여러 개의 도로가 존재한다. 결벽증이 있는 동원이는, 한번도 가지 않은 길을 무서워한다. 동원이는 항공대의 여러 도로들 중 $n-1$ 개의 도로를 선택해서 그 도로로만 다니기로 하였다.
어떠한 건물 $x$에서 어떠한 건물 $y$ 로 이동한다는 것은, $x$ 에 연결된 도로를 타고 다른 건물로 이동하는 것을 반복하여 $y$ 에 도달할 수 있다는 것이다. 예를 들어, $3$ 개의 건물이 있고, $(1, 2), (2, 3)$ 번 건물 사이에 도로가 있다면, $1$번 건물에서 $3$번 건물로 이동한다는 것은
한다는 것이다. 이 과정에서 $3$개의 건물과 $2$개의 도로를 거쳤다. 동원이는 도로를 섬세하게 골랐기 때문에, 동원이가 고른 $n-1$ 개의 도로들만을 사용해서, 임의의 건물 $i$ ($1 \le i \le n$) 에서 $j$ ($1 \le j \le n$) 으로 항상 이동할 수 있다.
한국항공대학교는 학생들의 편의를 위해서 도로들과 건물들을 공사하고 있다. 만약 어떠한 건물이나 도로가 공사중이라면, 이동을 할 때 이 건물이나 도로를 거쳐갈 수 없다. 이 조건에 따라 다음과 같은 $q$ 개의 질문을 해결하라.
1 i j k
: $k$ 번 건물이 공사 중일때, $i$ 번 건물에서 $j$ 번 건물로 이동할 수 있는가? ($1 \le i, j, k \le n$)2 i j k l
: $k$ 번 건물과 $l$ 번 건물을 잇는 도로가 공사 중일때, $i$ 번 건물에서 $j$ 번 건물로 이동할 수 있는가? 동원이가 고른 도로 중 $k$ 번 건물과 $l$ 번 건물을 잇는 도로가 존재함이 보장된다. ($1 \le i, j, k, l \le n$)첫 번째 줄에 정수 $n$ 이 주어진다. ($2 \le n \le 250\,000$)
이후 $n-1$ 개의 줄에 동원이가 고른 도로가 잇는 두 건물의 번호 $x, y$ 가 주어진다. ($1 \le x, y \le n, x \neq y$)
다음 줄에 정수 $q$ 가 주어진다. ($1 \le q \le 250\,000$)
이후 $q$ 개의 줄에 질문이 위에서 설명한 형식대로 주어진다.
$q$ 개의 줄에 걸쳐 질문의 정답을 YES
나 NO
로 출력하라.
4 1 2 2 3 2 4 13 1 1 3 1 1 1 3 2 1 1 3 3 1 1 3 4 1 1 1 2 1 1 1 1 2 1 2 2 4 2 1 2 1 2 2 1 3 1 2 2 1 3 2 3 2 1 3 2 4 2 1 1 1 2 2 1 1 2 4
NO NO NO YES YES NO YES NO NO NO YES YES YES