백준 24602번: Tree Hopping (C++)

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

24602번: Tree Hopping

---

Solved By: LCA, Sparse Table

 

각 노드 사이의 거리 값을 담을 배열을 선언하는 방법을 사용하지 않았습니다. 각 거리가 모두 1인 것을 활용합니다. 예를 들어 node a의 2^3번째 부모를 찾으려면 2^3만큼 이동해야 하기에 따로 메모리를 잡아먹을 배열을 사용하지 않았습니다.

#include <iostream>
#include <vector>
#include <memory.h>
#define MAX 100001
#define LOG_MAX 17
using namespace std;

vector<int> adj[MAX];
int T;

int parent[MAX][LOG_MAX];
int level[MAX];

void dfs(int now, int par){
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(next == par) continue;
        
        level[next] = level[now] + 1;
        parent[next][0] = now;
        dfs(next, now);
    }
}

void swap(int* a, int* b){
    int* temp = a;
    a = b;
    b = temp;
}

int distQ(int a, int b){
    int res = 0;
    
    if(level[a] < level[b]) swap(a, b);
    
    int diff = level[a] - level[b];
    
    for(int i = LOG_MAX - 1; i >= 0; i--){
        if(diff >= 1 << i){
            diff -= 1 << i;
            res += (1 << i);
            a = parent[a][i];
        }
    }
    
    if(a != b){
        for(int i = LOG_MAX - 1; i >= 0; i--){
            if(parent[a][i] != 0 && parent[a][i] != parent[b][i]){
                res += (1 << (i + 1));
                
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        
        res += 2;
    }
    
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> T;
    for(int t = 0; t < T; t++){
        int n; cin >> n;
        
        for(int i = 0; i < MAX; i++) adj[i].clear();
        
        for(int i = 0; i < n - 1; i++){
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        level[1] = 0;
        dfs(1, 0);
        
        vector<int> query;
        for(int i = 0; i < n; i++){
            int q; cin >> q;
            query.push_back(q);
        }
        
        for(int j = 1; j < LOG_MAX; j++){
            for(int i = 1; i <= n; i++){
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
        
        bool flag = 1;
        
        for(int i = 0; i < n - 1; i++){
            if(distQ(query[i], query[i + 1]) > 3){
                flag = 0; break;
            }
        }
        
        cout << flag << '\n';
    }
}