문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 LCA를 변형해서 풀어야 하는 문제이다.
  • 각 노드의 조상 2의 곱으로 저장할 뿐만 아니라 현재 노드부터 2의 곱 위치까지의 max와 min(M,m)을 저장해두어서 이용해야 한다.
  • LCA를 완벽하게 이해했다면 풀수 있는 아주 좋은 문제인 듯 하다!!
  • 예를 들어, 7번째 조상까지의 min과 max를 찾는다고 하면 7은 2^2 + 2^1 + 2^0 이므로 2의 2승까지의 min, max를 비교하고 거기서부터의 2의 1승까지의 min, max를 비교하고 마지막으로 2의 0승까지 있는 min, max를 비교하면 끝난다.
  • 내 코드는 BFS를 이용해서 트리를 만들어주고 두 노드의 깊이를 같게 해주고 2의 곱으로 LCA를 찾아주었다!

코드

#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
#define X first
#define Y second
using pii = pair<int, int>;

#define INF 1000000000
#define SIZE 100010


char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int N() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

vector< vector< pii > > ll;
int ac[17][SIZE], M[17][SIZE], m[17][SIZE];
int level[SIZE];
int n, k, v, w, u;


int LCA(int a, int b){
    int MAX = -INF, MIN = INF;
    int diff = level[a] - level[b];
    for(int i = 16; i >= 0; i--){
        if((1<<i) <= diff){
            MAX = max(MAX, M[i][a]);
            MIN = min(MIN, m[i][a]);
            a = ac[i][a];
            diff -= (1<<i);
        }
    }
    if(a == b) {
        printf("%d %d\n", MIN, MAX);
        return a;
    }
    for(int i = 16; i >= 0; i--){
        if(ac[i][a] != ac[i][b]){
            MAX = max(MAX, max(M[i][a], M[i][b]));
            MIN = min(MIN, min(m[i][a], m[i][b]));
            a = ac[i][a];
            b = ac[i][b];            
        } 
    } 
    MAX = max(MAX, max(M[0][a], M[0][b]));
    MIN = min(MIN, min(m[0][a], m[0][b]));
    printf("%d %d\n", MIN, MAX);
    return ac[0][a];
}

void build_tree(int root){
    queue<int> q;
    q.push(root);
    level[root] = 1;
    ac[0][root] = 1;
    
    while(!q.empty()){
        u = q.front(); q.pop();
        for(int i = 0; i < ll[u].size(); i++){
            v = ll[u][i].X, w = ll[u][i].Y;
            if(level[v] == 0){
                level[v] = level[u] + 1;
                ac[0][v] = u;
                m[0][v] = M[0][v] = w;
                q.push(v);
            }
        }
    }
}

void find_ac(){
    for(int i = 1; i < 17; i++){
        for(int j = 1; j < n + 1; j++){
            ac[i][j] = ac[i-1][ac[i-1][j]];
            M[i][j] = max(M[i-1][j], M[i-1][ac[i-1][j]]);
            m[i][j] = min(m[i-1][j], m[i-1][ac[i-1][j]]);
        }
    }
}

int main(){
    n = N();
    ll = vector< vector< pii > >(n + 1);
    for(int i = 1; i < n; i++){
        v = N(), u = N(), w = N(); 
        ll[v].push_back(pii(u, w));
        ll[u].push_back(pii(v, w));
    }

    build_tree(1);
    find_ac();  

    k = N();

    while(k--){
        v = N(), u = N(); 
        level[v] > level[u] ? LCA(v, u) : LCA(u, v);       
    }
}

느낀점

  • LCA를 확실히 정리하고 넘어가니까 여태까지 안풀리던 문제를 수월하게 풀어냈다.
  • 참 제대로 알고 쓰는 것과 그렇지 않은 것의 차이가 진짜 크다.
  • 내 머리 속에서 나온 것은 아니지만 깔끔하게 나만의 코드를 만들어 낼 수 있다는 사실에 감사했다!