BOJ11812: K진 트리

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

  • LCA의 열화판같은 문제.
  • Base를 안찾고 풀면 더 빨리 풀리긴 한다.
  • K가 1인 함정을 조심하자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

struct Notation {
  LL num, level;
};

class Tree {
  LL N, K;
  vector<LL> pows;
public:
  Tree(LL n, LL k);
  Notation tr(LL x);
  Notation up(Notation n);
};


Tree::Tree(LL n, LL k): N(n), K(k) {
  pows.push_back(1);
  for(LL x = K; pows.back() <= N; x *= K)
    pows.push_back(pows.back() + x);
}

Notation Tree::tr(LL x) {
  LL level = lower_bound(pows.begin(), pows.end(), x) - pows.begin();
  return {x - pows[level], level};
}

Notation Tree::up(Notation n) {
  return {n.num / K, n.level-1};
}

int main() {
  LL N, K, Q, a, b;
  scanf("%lld %lld %lld", &N, &K, &Q);
  if (K == 1) {
    for(int i = 0; i < Q; i++) {
      scanf("%lld %lld", &a, &b);
      if(a > b) swap(a,b);
      printf("%lld\n", b-a);
    }
  } else {
    Tree tree(N, K);
    for(int i = 0; i < Q; i++) {
      scanf("%lld %lld", &a, &b);
      Notation na = tree.tr(a), nb = tree.tr(b);
      if(na.level > nb.level)
        swap(na, nb);
      int ans = 0;
      while(nb.level > na.level)
        nb = tree.up(nb), ans++;
      while(na.num != nb.num)
        nb = tree.up(nb), na = tree.up(na), ans += 2;
      printf("%d\n", ans);
    }
  }
}