문제

문제 링크

문제 접근

  • 이 문제는 문제를 어떻게 접근할지 잘 생각해봐야 한다.
  • Union Find를 이용해서 오히려 Union 되있는것을 하나씩 부서가면서(Collapse) 진행하면 되지 않을까 생각했지만 그 또한 시간 초과를 발생시킨다.
  • 여기서 발상의 전환을 유발하는 내용이 문제 설명에 존재한다.

다음 (N-1)+Q개의 줄 중에서 N-1개는 (1)의 형태로, Q개는 (2)의 형태로 주어진다. (1) 두 정수 x와 b가 주어진다(x = 0, 2 ≤ b ≤ N).

  • 즉 결국에 모든 엣지는 삭제된다는 것이다.
  • 이를 역이용해서 질의의 내용을 역순으로 돌면서 삭제 되는 때에 Union 시켜주고 질의를 역으로 확인한다.
  • 그리고 이를 역순으로 출력하면 답을 찾을 수 있다.

코드

#include <cstdio>
#include <vector>

using namespace std;

int n, ans_n, q, x, a, b, c, d, par[200001], temp[200001], data[400002][2];

int find(int i){
    if(par[i] == i)return i;
    return par[i] = find(par[i]);
}

int main(){
    scanf("%d %d", &n, &q);
    vector<int> ans(q);
    par[1] = 1, temp[1] = 1;
    for(int i = 2; i <= n; i++){
        scanf("%d", &temp[i]);
        par[i] = i;
    }
    for(int i = 0; i < n + q - 1; i++){
        scanf("%d", &x);
        if(x) scanf("%d %d", &data[i][0], &data[i][1]);
        else scanf("%d", &data[i][0]);
    }
    for(int i = n + q - 2; i >= 0; i--){
        if(data[i][1]) ans[ans_n++] = find(data[i][0]) == find(data[i][1]);
        else par[data[i][0]] = temp[data[i][0]];
    }
    for(int i = ans.size() - 1; i >= 0; i--)printf("%s\n", ans[i] ? "YES" : "NO");
}

느낀점

  • 이걸 뒤집어서 하나씩 넣어볼 생각을 어떻게 중학생들이 한다는 말이지…
  • 참 갈길이 멀다! 이럴때면 너무 퍼지지만 그래도 화이팅이다.