백준 11812: K진 트리

문제

풀이

https://kibbomi.tistory.com/203 풀이 참고한 블로그
루트 노드를 0으로 시작 0 ~ N-1 (깊이의 시작 노드와 끝 노드를 규칙적으로 구할 수 있게 된다.)
각 노드의 번호(x)의 부모 노드는 (x-1)/k이다.
깊이가 2이상부터 시작 노드 번호는 부모 노드의 깊이의 노드들 중 가장 왼쪽 노드k+1이고,
끝 노드 번호는 부모 노드의 깊이의 노드들 중 가장 오른쪽 노드k+k이다.
left=leftk+1, right=rightk+k

---

코드

import java.io.*;
import java.util.*;

public class Main {

    static long n;
    static int k,q;

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st=new StringTokenizer(br.readLine());
        n=Long.parseLong(st.nextToken());
        k=Integer.parseInt(st.nextToken());
        q=Integer.parseInt(st.nextToken());

        while(q-->0){
            st=new StringTokenizer(br.readLine());
            long a=Long.parseLong(st.nextToken())-1;
            long b=Long.parseLong(st.nextToken())-1;
            System.out.println(getDistance(a,b));
        }
    }

    static long getDepth(long x){
        if(x==0)return 0;
        if(k==1){
            return x;
        }
        long depth=1;
        long left=1,right=k;
        while(!(left<=x && x<=right)){
            depth++;
            left=left*k+1;
            right=right*k+k;
        }
        return depth;
    }

    static long getParent(long x){
        if(x==0)return 0;
        else return (x-1)/k;
    }

    static long getDistance(long a,long b){
        long depthA,depthB,ans=0;

        depthA=getDepth(a);
        depthB=getDepth(b);

        if(k==1)return Math.abs(depthA-depthB);

        if(depthA<depthB){
            long tmp=a;
            a=b;
            b=tmp;

            tmp=depthB;
            depthB=depthA;
            depthA=tmp;
        }

        while(depthA!=depthB){
            --depthA;
            a=getParent(a);
            ++ans;
        }

        while(a!=b){
            ans+=2;
            a=getParent(a);
            b=getParent(b);
        }
        return ans;
    }

}

#LCA