백준 10838 트리 (C++)

https://www.acmicpc.net/problem/10838

10838번: 트리

lca를 이용하는 문제입니다.

 

level을 맞추는 lca를 사용해서 처음 풀었는데 시간초과가 났습니다. 문제에 힌트가 있는걸 처음에 놓쳤습니다. 질의에 사용되는 "노드 간의 거리는 1000이하" 를 통해 level을 맞추지 않아도 되는걸 느꼈습니다. 

 

이번 문제에서 느낀건 변경되는 트리에서 level을 바꾸는 작업은 시간이 많이드는 작업이라는 것이었습니다.(subtree 개수가 커질 수 있으므로) 

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<bitset>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int parent[100001];
int color[100001];
int parent2[100001];
int lca(int a,int b,int c){
    int temp=1000;
    while(temp--){
        parent2[a]=c;
        if(a==0) break;
        a=parent[a];
    }
    temp=1000;
    while(temp--){
        if(parent2[b]==c){
            return b;
        }
        b=parent[b];
    }
    return b;
}
int main(){
    fast_io();
    int N,K;
    cin>>N>>K;
    parent[0]=1e8;
    for(int x=1;x<=K;x++){
        int r,a,b;
        cin>>r>>a>>b;
        if(r==1){
            int c;
            cin>>c;
            int temp=lca(a,b,x);
            while(a!=temp){
                color[a]=c;
                a=parent[a];
            }
            while(b!=temp){
                color[b]=c;
                b=parent[b];
            }
        }
        if(r==2){
            parent[a]=b;
        }
        if(r==3){
            int temp=lca(a,b,x);
            set<int> solve;
            while(a!=temp){
                solve.insert(color[a]);
                a=parent[a];
            }
            while(b!=temp){
                solve.insert(color[b]);
                b=parent[b];
            }
            cout<<solve.size()<<'\n';
        }
    }
}