2997 : 트리(중등) 
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 139 회
- 시도횟수
- 774 회
문제
트리 정보가 주어지고, 에지의 제거 정보와 질의가 임의의 순서로 주어질 때,
작업을 순서대로 수행하며 질의에 대한 답을 출력하는 프로그램을 작성하시오.
입력형식
표준 입력으로 다음 정보가 주어진다.
첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N 과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다.
다음 N - 1 개의 줄의 i 번째 줄에는 정점 i + 1 의 부모 정점을 나타내는 정수 a 가 주어진다 (1 ≤ a ≤ N ).
다음 (N - 1) + Q 개의 줄 중에서 N - 1 개는 (1)의 형태로, Q 개는 (2)의 형태로 주어진다.
(1) 두 정수 x 와 b 가 주어진다 (x = 0, 2 ≤ b ≤ N ).
이것은 b 의 부모 정점과 b 를 연결하는 에지를 제거함을 의미한다. 각 줄의 b 는 모두 다르다.
(2) 세 정수 x, c, d 가 주어진다 (x = 1, 1 ≤ c, d ≤ N ).
이것은 c 와 d 를 연결하는 경로가 존재하는 지 묻는 질의를 의미한다.
출력형식
표준 출력으로 질의에 대한 답을 순서대로 Q개의 줄에 출력한다.
각 줄마다 경로가 존재하면 YES를 아니면 NO를 출력한다.
부분문제의 제약 조건
• 부분문제 1: 전체 점수 100점 중 9점에 해당하며 1 ≤ N ≤ 1,000, 1 ≤ Q ≤ 1,000 이고
정점 i 의 부모 정점은 정점 i - 1 이다(i = 2, ... , N).
• 부분문제 2: 전체 점수 100점 중 13점에 해당하며 1 ≤ N ≤ 1,000, 1 ≤ Q ≤ 1,000 이다.
• 부분문제 3: 전체 점수 100점 중 21점에 해당하며 1 ≤ N ≤ 3,000, 1 ≤ Q ≤ 200,000 이다.
• 부분문제 4: 전체 점수 100점 중 28점에 해당하며 루트를 제외한 모든 정점의 부모 정점은 서로 다르다.
• 부분문제 5: 전체 점수 100점 중 29점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.
입력 예3 3 1 1 1 2 3 0 3 1 2 3 1 1 2 0 2 |
출력 예YES NO YES |
입력 예11 5 7 4 1 9 11 1 11 1 3 7 0 11 1 8 5 1 3 9 0 10 0 9 0 7 1 2 7 0 5 1 1 10 0 8 0 6 0 2 1 1 3 0 3 0 4 |
출력 예NO YES YES NO YES |