6182 : 경로 압축 및 오프라인 쿼리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리 구조에서 간선을 제거하는 연산과 두 노드가 여전히 연결되어 있는지 확인하는 연산이 주어집니다. 쿼리를 역순으로 처리하며 분리 집합(Disjoint Set)을 합치는 기법을 활용하여 효율적으로 답하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N과 쿼리의 개수 Q (1 ≤ N, Q ≤ 100,000)가 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다. (간선 번호는 1번부터 N-1번까지 순서대로 매겨집니다.)
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
-
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다. (간선 번호는 1번부터 N-1번까지 순서대로 매겨집니다.)
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
1 u: u번 간선을 제거합니다.-
2 u v: u와 v가 같은 컴포넌트에 연결되어 있는지 확인합니다.출력 설명
2번 쿼리에 대해 연결되어 있다면 YES, 단절되었다면 NO를 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2
1 3
2 4
2 5
2 4 5
1 4
2 4 5
2 1 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES
NO
YES