만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

트리

시간 제한2초메모리 제한512 MB

요약
두 정점이 연결되어 있는지 묻는 질의를 처리한 뒤 답에 따라 트리에서 간선 하나를 제거할 수 있어, 온라인 삭제 상황에서 연결성을 관리해야 한다.
난이도

어려움10점 중 8점

유형
트리, 유니온 파인드, DFS, 구현
정답자
아직 제출이 없습니다

문제

트리 TT는 정점과 에지로 이루어진다. 그림 1의 원이 정점이고, 정점과 정점을 잇는 선이 에지다. 가장 위에 놓인 정점을 루트라 하며, 루트는 하나뿐이다. 정점 NN개에는 1번부터 NN번까지 번호가 붙고 루트는 항상 1번이다.

두 정점 vv와 ww를 잇는 경로는 정점을 나열한 순서열 (v0,v1,…,vm)(v_0, v_1, \dots, v_m)이다. 이웃한 viv_i와 vi+1v_{i+1}은 에지로 연결되어 있고, v0=vv_0 = v, vm=wv_m = w이다. 트리에서는 임의의 두 정점 사이에 이런 경로가 정확히 하나 있다. 그림 1에서 정점 3과 정점 11을 잇는 유일한 경로는 (3,4,1,7,11)(3, 4, 1, 7, 11)이다.

그림 1

정점 vv에서 루트까지 가는 유일한 경로를 PP라 하자. vv와 에지로 연결된 정점 가운데 PP 위에 있는 정점을 vv의 부모 정점이라 한다. 그림 1에서 4, 7, 9의 부모 정점은 1이고, 2와 11의 부모 정점은 7이다. 루트에는 부모 정점이 없다.

에지를 하나 제거하면 그 에지의 양 끝점 말고 다른 정점 쌍 사이에서도 경로가 사라질 수 있다. 그림 1에서 7과 11 사이의 에지를 제거하면 8과 5를 잇는 경로가 없어진다.

트리 정보가 주어지고, 이어서 질의와 에지 제거가 임의의 순서로 섞여 주어진다. 주어진 순서대로 작업을 처리하면서 각 질의의 답을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 트리의 정점 개수 NN과 질의 개수 QQ가 주어진다 (1≤N,Q≤200 0001 \le N, Q \le 200\,000).

다음 N−1N-1개 줄 가운데 ii번째 줄에는 정점 i+1i+1의 부모 정점 번호 aa가 주어진다 (1≤a≤N1 \le a \le N). 주어지는 부모 관계는 항상 1번 정점을 루트로 하는 트리를 이룬다.

다음 QQ개 줄에는 각각 세 정수 bb, cc, dd가 주어진다 (1≤b,c≤N1 \le b, c \le N, dd는 0 또는 1). d=0d = 0이면 bb와 cc를 잇는 경로가 있는지 묻는 질의만 처리한다. d=1d = 1이면 같은 질의를 먼저 처리한 뒤, 답이 YES이면 bb와 bb의 부모 정점을 잇는 에지를 제거하고, 답이 NO이면 cc와 cc의 부모 정점을 잇는 에지를 제거한다. 제거하려는 에지가 원래 없거나 이미 제거되었으면 아무 에지도 제거하지 않는다.

출력

질의 QQ개의 답을 순서대로 QQ개 줄에 출력한다. 경로가 있으면 YES를, 없으면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    3 4
1
1
2 3 1
1 3 0
2 3 1
1 3 1
    예상 출력
    YES
YES
NO
NO

  2. 예제 2

    입력
    11 7
7
4
1
9
11
1
11
1
3
7
11 9 1
8 5 0
3 9 0
6 3 1
10 9 1
3 10 1
1 4 1
    예상 출력
    YES
NO
YES
NO
NO
YES
YES