Boj 11812) K진 트리

문제

백준 11812

설명

K진 트리의 부모노드에 대한 점화식만 알면 간단하게 풀 수 있는 문제.

전략은 LCA 알고리즘의 변형으로, 먼저 두 노드를 같은 높이로 맞추고, 두 노드가 같아질 때까지 부모로 회귀한다.

주의해야할 점은 K=1 일때 LCA() 를 쓰면 시간초과가 난다는 점으로, 그냥 뺄셈으로 해결하면 된다.

시간 복잡도

O(\(\log_{\mathrm{K}}{\mathrm{N}}\))

• 단 \(\mathrm{K}=1\) 일 땐 O(1)

코드

using ll = long long;

ll K, N;

int Height(ll idx)
{
	int res = -1; ll base = 1;
	while (idx > 0)
	{
		res++;
		idx -= base;
		base *= K;
	}
	return res;
}

ll Parent(ll idx)
{
	return (idx + (K - 2)) / K;
}

int LCA(ll a, ll b)
{
	ll res = 0;
	int h_a = Height(a), h_b = Height(b);
	if (h_a < h_b) { swap(a, b); swap(h_a, h_b); }
	
	int dff = h_a - h_b;	
	for (int i = 0; i < dff; i++)
	{
		a = Parent(a);
		h_a--;
		res++;
	}
	
	while (a != b)
	{
		a = Parent(a);
		b = Parent(b);
		h_a--;
		res += 2;
	}
	
	return res;
}

int main()
{
	int Q;
	cin >> N >> K >> Q;

	while (Q--)
	{
		ll a, b;
		cin >> a >> b;
		if (K > 1)
			cout << LCA(a, b) << '\n';
		else cout << abs(a - b) << '\n';
	}
}