백준(boj)10838 - 트리

문제 링크 - https://www.acmicpc.net/problem/10838

👀문제이해 및 풀이방법

lca문제이다 근데 지금까지 알고있던 lca가 아니다 고생을 좀 했다
중요한건 lca(a,b의 최단경로의 길이)가 1000개 안에 있다는 것과 depth를 사용하면 안된다는 것이다

해보면 알겠지만 depth를 업데이트 하면서 풀면 바로 시간초과다 그래서 1000개 안에 lca가 있다는 조건을 주어준것 같다
코드를 몇번을 갈아엎었는데 후.. 별로 좋은문제는 아닌 것 같다 그냥 출제자의 입맛에 맞춰 풀어야하는 느낌이다😥

문제를 이해 했다면 depth따위 없이 노드에 ‘부모노드’와 ‘부모노드와 이어지는 간선의 색’ 딱 2개만 저장하여 풀어보면 생각보다 쉽게 풀린다
누가봐도 lca문제에 lca를 사용하면 시간초과 나고 depth없이 for문으로 1000번 돌려서 lca를 찾게 만든 문제가 맞나 싶다
lca를 찾을 때에는 N개짜리 visit배열(코드에서는 find라는이름으로 씀)을 선언하고 a를1000번 돌려서 visit채우고 b를 1000번 돌려서 가장 처름 만나는 곳이 lca이다
진땀 뺀 문제였다🔥

📝코드

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
struct _node{
    int parent=0;
    int color=0;
};
class tree_query{
private:
    vector<_node> tree;
    int N,K;
public:
    tree_query(){
        std::cin >> N >> K;
        tree.resize(N);
    }
    void query(){
        int q,a,b,c;
        for(int i=0;i<K;i++){
            std::cin >> q;
            if(q ==1){
                std::cin >> a >> b >> c;
                paint(a,b,c);
            }
            else if(q==2){
                std::cin >> a>> b;
                move(a,b);
            }
            else if(q==3){
                std::cin >>a >> b;
                std::cout << count(a,b) << '\n';
            }
        }
    }
    int find_lca(int a,int b){
        vector<bool> find(N,false);
        for(int i=0;i<1000;i++){
            find[a]=true;
            a=tree[a].parent;
        }
        for(int i=0;i<1000;i++){
            if(find[b])
                return b;
            b=tree[b].parent;
        }
        return 0;
    }
    void paint(int a,int b,int c){
        int lca = find_lca(a,b);
        while(a!=lca){
            tree[a].color=c;
            a=tree[a].parent;
        }
        while(b!=lca){
            tree[b].color=c;
            b=tree[b].parent;
        }

    }
    void move(int a,int b){
        tree[a].parent=b;
    }
    int count(int a,int b){
        unordered_set<int> S;
        int lca =find_lca(a,b);
        while(a!=lca){
            S.insert(tree[a].color);
            a=tree[a].parent;
        }
        while(b!=lca){
            S.insert(tree[b].color);
            b=tree[b].parent;
        }
        return S.size();
    }
};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    tree_query tq;
    tq.query();
    return 0;
}