백준 11812 K진 트리

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

LCA 개념을 알면 쉽게 풀 수 있는 문제지만, sparse table이 필요 없으면서도 노드가 $ {10^{15}} $ 개나 되는 참신한 문제이다.

LCA에서는 원하는 조상을 빠르게 찾기 위해 sparse table을 사용했지만 이 문제에서는 sparse table 없이도 부모와 자식의 관계가 예쁜 수식으로 나오기 때문에 조상을 $log(n)$만에 찾을 수 있다.

문제에서 나오는 트리의 숫자에서 모두 1을 빼보자. 어떤 노드 x에 자식들은 kx+1 부터 kx+k임을 알 수 있다. 따라서 우리는 어떤 노드 n의 부모를 (n-1)/k라는 수식으로 알아낼 수 있다.마찬가지로 어떤 노드 n의 조상은 $(n-1)/k^p$ 이며 p는 log(n)에 비례하므로 log(n)만에 원하는 조상을 찾을 수 있다.(노드의 개수가 1인 경우 제외)

노드의 경우가 1인 경우는 두 노드의 차이가 거리이므로 쉽게 예외처리가 가능하다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,q;
ll calc_lv(ll x){
	ll tmp=0;
	while(x>0LL){
		x=(x-1LL)/k;
		tmp++;
	}
	return tmp;
}
ll lca(ll x, ll y){
	ll lx=calc_lv(x);
	ll ly=calc_lv(y);
	if(lx<ly){
		swap(x,y);
		swap(lx,ly);
	}
	while(lx>ly){
		x=(x-1LL)/k;
		lx--;
	}
	while(x!=y){
		x=(x-1LL)/k;
		y=(y-1LL)/k;
	}
	return x;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>k>>q;
	while(q--){
		ll x,y; cin>>x>>y;
		x--; y--;
		if(k==1) cout<<llabs(x-y)<<'\n';
		else cout<<calc_lv(x)+calc_lv(y)-2*calc_lv(lca(x,y))<<'\n';
	}
	return 0;
}