BAEKJOON 15480번: LCA와 쿼리

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

15480번: LCA와 쿼리

 

풀이를 위한 발상

한 정점을 루트로 하는 트리에서 다른 두 정점의 LCA를 찾아야 한다.

조금 생각을 해보면, 이때의 LCA는 세 정점의 접합점이라는 것을 알 수 있다.

조금 더 구체적으로 표현하자면 다음과 같다.

한 정점으로 트리를 분할했을 때, 정점 r, u, v는 모두 서로 다른 서브 트리에 존재할 수 있게 하는 정점.

 

이를 토대로 생각하면, 아무 노드나 잡고 depth를 설정해준 후, LCA(r, u), LCA(u, v), LCA(v, r) 중 depth 가 가장 깊은 것이 정답이다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
const int sz=1e5+3;
int anc[sz][20],dep[sz];
vector<int>vi[sz];
int f(int u,int v){
    int i=0;
    if(dep[u]==dep[v])return v;
    while(dep[u]<dep[anc[v][i+1]])i++;
    return f(u,anc[v][i]);
}
int g(int u,int v){
    int i=0;
    if(u==v)return v;
    while(anc[u][i+1]!=anc[v][i+1])i++;
    return g(anc[u][i],anc[v][i]);
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    v=f(u,v);
    return g(u,v);
}
int main(){
    int N;scanf("%d",&N);
    for(int i=1;i<N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        vi[u].push_back(v);
        vi[v].push_back(u);
    }
    queue<int>q;q.push(1);
    dep[1]=1;
    while(!q.empty()){
        int cur=q.front();q.pop();
        for(int i=0;i<(int)vi[cur].size();i++){
            int nxt=vi[cur][i];
            if(dep[nxt])continue;
            dep[nxt]=dep[cur]+1;
            anc[nxt][0]=cur;
            int k=cur,r=0;
            while(anc[k][r]){
                k=anc[k][r++];
                anc[nxt][r]=k;
            }
            q.push(nxt);
        }
    }
    int M;scanf("%d",&M);
    for(int i=1;i<=M;i++){
        int r,u,v,ru,uv,vr,ans;
        scanf("%d%d%d",&r,&u,&v);
        ru=lca(r,u),uv=lca(u,v),vr=lca(v,r);
        if(dep[ru]>=dep[uv]){
            if(dep[ru]>=dep[vr])ans=ru;
            else if(dep[vr]>=dep[uv])ans=vr;
        }else{
            if(dep[uv]>=dep[vr])ans=uv;
            else if(dep[vr]>=dep[ru])ans=vr;
        }
        printf("%d\n",ans);
    }
    return 0;
}