11812번: K진 트리

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


$O(q\lg _k{n})$

노드 번호가 1번부터 시작한다면 x의 부모는 (x-2)/k+1
두 노드의 공통 조상을 찾기 위해선 큰 번호의 노드를 부모로 거슬러 올리는 것을 반복하면 된다.
k=1인 경우에 이 방법으로는 시간초과가 날 수 있으므로 따로 처리해야한다.

#include<cstdio>
#include<algorithm>
using namespace std;
long long n, x, y;
int k, q;
int main() {
    scanf("%d%d%d", &n, &k, &q);
    for (; q--;) {
        scanf("%lld%lld", &x, &y);
        if (k<2) {
            printf("%lld\n", abs(x - y));
            continue;
        }
        int r = 0;
        while (x^y) {
            if (x<y) swap(x, y);
            x = (x - 2) / k + 1;
            r++;
        }
        printf("%d\n", r);
    }
    return 0;
}