BOJ 1646 - 피이보나치 트리

BOJ 1646 - 피이보나치 트리

재귀적으로 트리를 잘 구성하는 문제이다.

일단 $S, E$ 로 가는 경로를 모두 재귀함수로 얻어낸다.

이 문자열을 $s, e$ 라고 하자.

$s, e$의 동일한 prefix는 루트부터 $lca(S, E)$ 까지 가는 동일한 경로이므로 모두 삭제해준다.

이후에 $s$의 길이만큼 $U$ 를 출력하고 $e$ 를 출력하면 된다.

$S$ 에서 $lca(S,E)$ 까지는 항상 $U$로 올라가면 되고, 거기서부터 $E$까지 가는 경로가 $e$에 남아있기 때문이다.

정점이 굉장히 많아도 이 피이보나치 트리라는 것의 특성상 트리의 Level이 낮게 제한되기 때문에(아니 그렇지 않으면 출력을 할 수 없겠지), 시간복잡도는 문제없다.

int tsize[100];
void solve() {
   tsize[0] = 1;
   tsize[1] = 1;
   tsize[2] = 3;
   for (int i = 3; i <= 50; i++) tsize[i] = 1 + (i >= 2 ? tsize[i - 2] : 0) + (i >= 1 ? tsize[i - 1] : 0);

   int n, s, e;
   cin >> n >> s >> e;
   s--, e--;
   if (s == e) {
      return;
   }
   string spath, epath;
   function<void(int, int, int, int, string &)> get_path = [&](int level, int l, int r, int k, string &path) -> void {
      int left_size = (level >= 2 ? tsize[level - 2] : 0);
      int right_size = (level >= 1 ? tsize[level - 1] : 0);
      //assert(left_size + right_size + 1 == r - l + 1);
      int par = l;
      if (par == k) return;
      int lstart = l + 1;
      int lend = l + left_size;
      int rstart = lend + 1;
      int rend = r;
      if (k <= lend) {
         path += 'L';
         get_path(level - 2, lstart, lend, k, path);
      } else {
         path += 'R';
         get_path(level - 1, rstart, rend, k, path);
      }
   };
   get_path(n, 0, tsize[n] - 1, s, spath);
   get_path(n, 0, tsize[n] - 1, e, epath);
   reverse(all(spath));
   reverse(all(epath));
   while (sz(spath) && sz(epath)) {
      if (spath.back() == epath.back()) {
         spath.pop_back();
         epath.pop_back();
      } else break;
   }
   reverse(all(spath));
   reverse(all(epath));
   string spath2;

   cout << string(sz(spath), 'U') + epath;
}