백준 23355번: 공사 (C++)

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

23355번: 공사

---

Solved By: LCA

 

첫 시작은 Sparse Table로 LCA를 구한다면 x와 y 사이 경로에 k의 존재를 알 수 없을 거 같아서 Sparse Table을 사용하지 않고 LCA를 짰다가 시간 초과를 받았습니다.

 

그렇다면 \(Sparse Table\)이 필요하다고 느끼는데 경로 사이에 k가 존재하는 법을 알 수가 없어서 구글의 도움을 받았습니다.

다음과 같은 성질을 가지고서 문제를 풀 수 있습니다.

 

Solution

 

k가 x에서 y로 가는 경로 사이에 존재한다면 x와 y는 k의 하위 트리에 존재한다.

즉, \(LCA(x, k) = k\), 혹은 \(LCA(y, k) = k\)라면 k는 x와 y사이의 경로에 존재한다고 볼 수 있습니다.

하지만, 예외가 존재합니다.

\(LCA(x, y) = k\)의 level이 k의 level보다 크다면 k는 \(LCA(x, y)\)의 parent node들 중의 하나이므로 x와 y사이의 경로에 속하지 않습니다.

 

2번째 쿼리는 조금 더 복잡해집니다. 

k와 l 둘 다 예외에 따라 level을 체크하여 경로에 존재하는지 확인합니다. >> 둘 다 더 작거나 같다면 통과할 수 있음.

\(LCA(x, k) = k\)이고, \(LCA(x, l) = l\)이면 x와 \(LCA(x, y)\) 사이에 k-l 경로가 있다는 뜻입니다.

\(LCA(y, k) = k\)이고, \(LCA(y, l) = l\)이면 y와 \(LCA(x, y)\) 사이에 k-l 경로가 있다는 뜻입니다.

그럼 x와 lca(x, y) 사이에 k가 있고, y와 lca(x, y) 사이에 l이 있는 경우는 어떡할까요?

>> 애초에 그런 경우가 없습니다. 

 

#include <iostream>
#include <vector>
#define MAX 250001
#define LOG_MAX 18
using namespace std;

vector<int> adj[MAX];
int parent[MAX][LOG_MAX];
int level[MAX];
int n, q;

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

int getLCA(int a, int b){
    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;
            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]){
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        
        a = parent[a][0];
    }
    
    return a;
}

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);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    dfs(1, -1);
    
    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];
        }
    }
    
    cin >> q;
    for(int i = 0; i < q; i++){
        int query; cin >> query;
        if(query == 1){
            int x, y, k; cin >> x >> y >> k;
            if(level[getLCA(x, y)] > level[k]) cout << "YES";
            else if(getLCA(x, k) == k || getLCA(y, k) == k) cout << "NO";
            else cout << "YES";
        }
        else{
            int x, y, k, l; cin >> x >> y >> k >> l;
            if(level[getLCA(x, y)] >= level[k] && level[getLCA(x, y)] >= level[l]) cout << "YES";
            else if(getLCA(x, k) == k && getLCA(x, l) == l) cout << "NO";
            else if(getLCA(y, k) == k && getLCA(y, l) == l) cout << "NO";
            else cout << "YES";
        }
        cout << "\n";
    }
    
    return 0;
}