p5903 树上k级祖先

(Updated: )
(5 mins to read)

使用倍增每次可以在logn的时间内解决，而使用长链剖分，可以在O(nlogn)预处理后，O(1)回答询问，虽然在实践中相差无几，也不太可能要求O(1),但是长剖的这种做法以及预处理的方法还是很巧妙的

  • 预处理出倍增数组，长链的长度以及链顶节点，再预处理出每个数字的最高二级制位hb[i]，如果当前节点为链顶节点，预处理出其向上(跳fa)和向下(跳son)len[u]-1个节点
  • 处理询问时，先利用倍增数组跳到(1<<hb[i])的祖先处，此时k’=k-(1<<hb[i]) < (1<<hb[i])
  • 当前所在的长链的长度一定是大于k’的，所以考虑跳到链顶，而后根据剩余的k选择向上还是向下跳，此时利用预处理出的up，dwn数组即可实现O(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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 5e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, q, hb[N], fa[N][22], rt;
int len[N], dep[N], top[N], son[N];
unsigned int s;
vector<int> G[N], up[N], dwn[N];
inline unsigned int get(unsigned int x)
{
  x ^= x << 13;
  x ^= x >> 17;
  x ^= x << 5;
  return s = x;
}
void dfs1(int u)
{
  dep[u] = dep[fa[u][0]] + 1;
  for(int v : G[u])
  {
    if(v==fa[u][0]) continue;
    for(int i=0; fa[v][i]; i++) fa[v][i+1] = fa[fa[v][i]][i];
    dfs1(v);
    if(len[v]>len[son[u]]) son[u] = v;
  }
  len[u] = len[son[u]] + 1;
}
void dfs2(int u, int t)
{
  top[u] = t;
  if(u==t)
  {
    for(int i=0, j=u; i<len[u]; i++)
      up[u].pb(j), j = fa[j][0];
    for(int i=0, j=u; i<len[u]; i++)
      dwn[u].pb(j), j = son[j];
  }
  if(son[u]) dfs2(son[u], t);
  for(int v : G[u])
    if(v!=son[u])
      dfs2(v, v);
  return;
}
int ask(int x, int k)
{
  if(!k) return x;
  x = fa[x][hb[k]], k -= (1<<hb[k]);
  k -= dep[x] - dep[top[x]], x = top[x];
  return k>=0 ? up[x][k] : dwn[x][-k];
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q >> s;
  hb[0] = -1;
  for(int i=1; i<=n; i++)
  {
    cin >> fa[i][0];
    if(!fa[i][0]) rt = i;
    else G[fa[i][0]].pb(i);
    hb[i] = hb[i>>1] + 1;
  }
  dfs1(rt); dfs2(rt, rt);
  int ans = 0;
  ll res = 0;
  for(int i=1; i<=q; i++)
  {
    int x = (get(s)^ans)%n + 1;
    int k = (get(s)^ans)%dep[x];
    res ^= 1ll*i*(ans=ask(x, k));
  }
  cout << res << '\n';
  return 0;
}