백준 17469 : 트리의 색깔과 쿼리

17469번: 트리의 색깔과 쿼리 (acmicpc.net)

17469번: 트리의 색깔과 쿼리

풀이
쿼리 1 x : x와 x의 부모를 잇는 간선 삭제
=> 오프라인 쿼리로 처리했을 시 거꾸로 x와 x의 부모를 잇는 간선을 추가하는것으로 바꿀 수 있음
쿼리 2 x : x와 연결되어있는 모든 노드들의 색의 종류
=> 트리의 특성 상 x의 가장 최상단 부모의 모든 자식들과 연결할 수 있음 = 최상단 부모의 자식 노드들의 색의 종류를 구하는 것과 같다.

문제 포인트
1번 쿼리는 총 n-1개 주어진다 = 트리의 간선은 n-1개이며 오프라인 쿼리로 뒤에서부터 처리 할 시 처음엔 아무것도 연결되지 않은 상태로 볼 수 있음
부모와 자식을 연결 할 때는 유니온 파인드를 사용하며 set을 이용해 중복 체크를 한다.
이 때 set끼리 합칠 때 set이 작은쪽부터 큰쪽으로 합치는것이 시간적으로 최적이다. 단순히 합친다면 최악의 경우 n^2이 나오지만 작은쪽에서 큰쪽으로 합친다면 nlogn이 나온다.
참고 : https://ryute.tistory.com/52

간선을 하나씩 추가해가며 정답을 구하고 역순으로 출력한다.

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 5000001
#define INF 2000000000
#define MOD 1000000
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }


int pnode[100001];
set<int>* child[100001];
int parent[100001];
int color[100001];
int getParent(int x) {
    if (x == parent[x])
        return x;
    else return parent[x] = getParent(parent[x]);
}

void unionParent(int p,int c) {
    p = getParent(p);
    c = getParent(c);

    if (p == c)
        return;

    if (child[p]->size() < child[c]->size()) {
        swap(child[p], child[c]);
    }

    for (auto i : *child[c]) {
        child[p]->insert(i);
    }
    child[c]->clear();

    parent[c] = p;
}
int main() {
    init();
    int n, q; cin >> n >> q;
    vector<pii> cmd;
    vector<int> ans;
    //부모 입력받기
    for (int i = 2; i <= n; i++) {
        cin >> pnode[i];
        pnodeSub[i] = pnode[i];
    }
    //색 입력받기
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
    }
    //초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        child[i] = new set<int>();
        child[i]->insert(color[i]);
    }

    for (int i = 0; i < n + q - 1; i++) {
        int qn, node; cin >> qn >> node;
        cmd.push_back({ qn,node });
    }

    for (int i = cmd.size() - 1; i >= 0; i--) {
        int qn = cmd[i].first;
        int node = cmd[i].second;
        if (qn == 1) {
            unionParent(pnode[node], node);
        }
        else {
            ans.push_back(child[getParent(node)]->size());
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << "\n";
    }
}