关于“树上 k 级祖先”问题的研究

发布于

方法 0

直接长链剖分,常数大
时间复杂度 $\Theta\left(n \log n + q\right)$

方法 1

直接倍增
时间复杂度 $\Theta\left(n \log n + q \log n\right)$

方法 2

使用重链剖分,跳到刚好超过 $k$ 级的链的顶端,然后通过 dfs 序推 $k$ 级祖先。
时间复杂度 $\mathcal O\left(n + q \log n\right)$

方法 3

考虑优化方法 2。可以二分刚好超过 $k$ 级的链,这样找这条链的时间复杂度就从 $\mathcal O\left(\log n\right)$ 降至了 $\mathcal O\left(\log \log n\right)$,但是常数较大
时间复杂度 $\mathcal O\left(n + q \log \log n\right)$

方法 4

考虑优化方法 2。往上跳重链的时候分块跳,每次跳 $\sqrt{\log n}$ 条链。需要预处理每个点的 $\sqrt{\log n}$ 级祖先。常数很小,是我在数据随机的情况下测试的最快的做法。
时间复杂度 $\Theta\left(n \sqrt{\log n} + q \sqrt{\log n}\right)$
代码:

// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom come.

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <tuple>
#include <vector>
#define gex(a, b, func) a = func(a, b)
// #define EFILE ""

using namespace std;
using tp = long long;

template <typename _Type, size_t _Size>
struct mray : array<_Type, _Size + 9> {
  _Type& operator[](size_t index) { return this->at(index); }
};

void DEMONS() {
}
// Constants
static constexpr tp Hat_N = 5e5;

// Classes

// Typedeves

// Variables
tp n, m, rt, cnt, las, ans, len;

// Arrays
mray<tp, Hat_N> hson, dep, top, fa, id, toid, up;
mray<vector<tp>, Hat_N> tr;

// Functions
tp dfs1(tp x, tp f) {
  tp temp = -1, s = 1;
  dep[x] = dep[f] + 1;
  for (auto&& i : tr[x]) {
    if (i != f) {
      tp si = dfs1(i, x);
      fa[i] = x;
      s += si;
      if (temp < si) {
        hson[x] = i;
        temp = si;
      }
    }
  }
  return s;
}

void dfs2(tp x, tp h) {
  top[toid[id[x] = ++cnt] = x] = h;
  if (hson[x]) dfs2(hson[x], h);
  if (x == top[x]) {
    up[x] = x;
    for (int i = 1; i <= len && top[fa[up[x]]] != 1; ++i) up[x] = top[fa[up[x]]];
  } else up[x] = up[top[x]];
  for (auto&& i : tr[x]) {
    if (i != fa[x] && i != hson[x]) dfs2(i, i);
  }
}

tp jump(tp x, tp k) {
  while (k >= dep[x] - dep[up[x]] + 1) {
    k -= dep[x] - dep[up[x]] + 1;
    x = fa[up[x]];
  }
  while (k >= id[x] - id[top[x]] + 1) {
    k -= id[x] - id[top[x]] + 1;
    x = fa[top[x]];
  }
  return toid[id[x] - k];
}

void IMAGINARY([[maybe_unused]] tp TEST_NUMBER) {
  cin >> n >> m;
  len = sqrt(log2(n));
  for (tp i = 1; i <= n; ++i) {
    tp f;
    cin >> f;
    if (!f) rt = i;
    else {
      tr[i].push_back(f);
      tr[f].push_back(i);
    }
  }
  dfs1(rt, rt);
  dfs2(rt, rt);
  while (m--) {
    tp u, v;
    cin >> u >> v;
    cout << jump(u, v) << ' ';
  }
  cout << '\n';
}

#include <fstream>

signed main() {
  tp t = 0, _t = 1;
  ios::sync_with_stdio(0);
  cin.tie(0);
#if !_CONSOLE
#ifdef _LOCAL
  static ifstream _in("input.in");
  cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
  static ifstream _in(EFILE ".in");
  static ofstream _out(EFILE ".out");
  cin.rdbuf(_in.rdbuf());
  cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
  // cin >> _t;
  DEMONS();
  while (t < _t) IMAGINARY(++t);
  return 0;
}

//*/

暂无评论

发表评论