[c++] 백준 #17399 트리의 외심 (190826)

< 풀이 >

직관대로 풀면 되는 문제. 단 case 처리 시 조금 까다로운 면이 있다. 외심 후보 3개를 두 점의 중점으로 고르고 나머지 한 점에서의 거리와 두 점에서의 거리가 같은 지 비교하면 끝.

만약 3개의 점 중 2개의 점이 동일한 경우에는 한번만 get_center해주면 됨. 3개의 점이 다 동일한 경우에는 그냥 그 점을 출력.

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define swap(a,b){int t=a; a=b; b=t;}
#define N_MAX 100010
int N, Q;
vector<int> graph[N_MAX];
// depth :: 노드의 깊이(레벨)
// ac[x][y] :: x의 2^y번째 조상을 의미 : sparse table
int depth[N_MAX];
int ac[N_MAX][25];

int max_level = (int)floor(log2(N_MAX));

void DFS(int here, int parent){
    depth[here] = depth[parent] + 1;
    
    // 나의 1번째 조상은 부모
    ac[here][0] = parent;

    for(int i=1; i<=max_level;i++){
        int prev = ac[here][i-1];
        ac[here][i] = ac[prev][i-1];
    }

    int len = graph[here].size();
    for (int i=0; i<len; i++){
        int next = graph[here][i];
        if (next == parent) continue;
        DFS(next, here);
    }
}

int get_lca(int c, int d){
    // lca를 구한다
    // 1) 같은 depth까지 끌어 올린다
    if (depth[c] != depth[d]){
        if (depth[c] > depth[d]) swap(c,d); // 항상 depth d가 더 크게
        for(int i=max_level;i>=0;i--){
            if(depth[c] <= depth[ac[d][i]]){
                d = ac[d][i];
            }
        }
    }
    int lca = c;
    // 2) 같은 depth라면 lca를 찾는다
    if (c != d){
        for(int i=max_level; i>=0; i--){
            if (ac[c][i] != ac[d][i]){
                c = ac[c][i];
                d = ac[d][i];
            }
            lca = ac[c][i];
        }
    }
    return lca;
}

int get_distance(int a, int b){
    if (a == -1 || b == -1) return -1;
    int lca = get_lca(a, b);
    return depth[a] + depth[b] - 2* depth[lca]+1;
}

// 외심을 구하는 함수
int get_center(int a, int b){
    if (a > b) { // swap : 항상 a <= b가 되도록
        swap(a,b);
    }
    int lca = get_lca(a, b);
    int total_dist = depth[a] + depth[b] - 2* depth[lca]+1;
    if ((total_dist % 2) == 0) return -1; // 짝수 distance는 있을 수 없다
    int k = (total_dist + 1) / 2;
    int k_th = 0;
    // trace number + k를 구한다.(k번째는 중앙점)
    if (depth[a]-depth[lca] + 1 >= k){ // c~lca 사이에 k가 있다
        k--;
        k_th = a;
        for(int i=max_level; i>=0; i--){
            if((1 << i) <= k){ // 2^i < k이면
                k -= (1 << i);
                k_th = ac[k_th][i];
            }
        }
    }
    else { // lca ~ d 사이에 k가 있다
        k_th = b;
        // 전체 경로 길이 - k값
        k = depth[a] + depth[b] - 2*depth[lca] - (k - 1);
        for(int i=max_level;i>=0;i--){
            if((1 << i) <= k){ // 2^i < k이면
                k -= (1 << i);
                k_th = ac[k_th][i]; // d에서부터 위로 올린다
            }
        }
    }
    return k_th;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for(int i=1; i<N;i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // 1번 root의 depth가 0이 되도록 하기 위해서임.
    depth[0] = -1;
    DFS(1,0);

    cin >> Q;
    while(Q--){
        int a, b, c;
        cin >> a >> b >> c;
        if (a == b && b == c) {
            cout << a << '\n';
        }
        else if (a == b || b == c || c == a) {
            int small = min(a, b); small = min(small, c); // 두 점 중 작은 게 a
            int big = max(b, a); big = max(big, c); // 두 점 중 큰 게 b
            cout << get_center(small, big) << '\n';
        }
        else { // a != b != c
            int ab_center = get_center(a,b);
            int bc_center = get_center(b,c);
            int ca_center = get_center(c,a);
            // ab ~ center 거리랑 c랑 ~ center 거리
            if (get_distance(a,ab_center) == get_distance(c,ab_center)){
                cout << ab_center << '\n';
            }
            else if (get_distance(b,bc_center) == get_distance(a,bc_center)){
                cout << bc_center << '\n';
            }
            else if (get_distance(c,ca_center) == get_distance(b,ca_center)){
                cout << ca_center << '\n';
            }
            else {
                cout << -1 << '\n';
            }
        }
    }
    return 0;
}