1 条题解
-
1
思路
长链剖分模板题。
长链剖分:
- 计算 表示 的 级祖先;
- 计算 表示 的 级祖先;
- 计算 表示在长链上从 向下走 步到达的祖先。
- 计算 的 级祖先,先让 跳到 级祖先, 减去 ,再让 跳到长链顶端, 减去 ,最后如果 ,那么答案就是 ,否则 ,答案就是 。
代码
// Problem: P5903 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P5903 // Memory Limit: 500 MB // Time Limit: 3000 ms #include <bits/stdc++.h> using namespace std; using uint = unsigned int; #define int long long const int N = 500010, M = 20; struct edge { int to, next; } e[N]; int head[N], idx; void add(int u, int v) { idx++; e[idx].to = v; e[idx].next = head[u]; head[u] = idx; } int n, q, s; uint get_rand(uint x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return s = x; } int rt; int fa[N][M]; void initfa() { for (int j = 1; j < M; j++) { for (int i = 1; i <= n; i++) { fa[i][j] = fa[fa[i][j - 1]][j - 1]; } } } int dep[N], ds[N], son[N]; void dfs(int u) { dep[u] = ds[u] = dep[fa[u][0]] + 1; for (int i = head[u]; i; i = e[i].next) { int to = e[i].to; dfs(to); if (ds[to] > ds[u]) { ds[u] = ds[to]; son[u] = to; } } } vector<int> up[N]; vector<int> down[N]; int belong[N]; void init(int u, int p) { belong[u] = p; if (u == p) { int tmp = u; for (int i = 0; i <= ds[u] - dep[u]; i++) { up[u].push_back(tmp); tmp = fa[tmp][0]; } tmp = u; for (int i = 0; i <= ds[u] - dep[u]; i++) { down[u].push_back(tmp); tmp = son[tmp]; } } if (son[u]) init(son[u], p); for (int i = head[u]; i; i = e[i].next) { int to = e[i].to; if (to == son[u]) continue; init(to, to); } } int query(int u, int k) { if (!k) return u; u = fa[u][__lg(k)]; k -= 1 << (__lg(k)); k -= dep[u] - dep[belong[u]]; u = belong[u]; if (k >= 0) return up[u][k]; else return down[u][-k]; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q >> s; for (int i = 1; i <= n; i++) { cin >> fa[i][0]; if (!fa[i][0]) rt = i; if (fa[i][0]) add(fa[i][0], i); } initfa(); dfs(rt); init(rt, rt); int ans = 0, res = 0; int x, k; for (int i = 1; i <= q; i++) { x = ((get_rand(s) ^ ans) % n) + 1; k = ((get_rand(s) ^ ans) % dep[x]); ans = query(x, k); res ^= (i * ans); } cout << res << '\n'; return 0; }
- 1
信息
- ID
- 4821
- 时间
- 3000ms
- 内存
- 500MiB
- 难度
- 5
- 标签
- 递交数
- 15
- 已通过
- 2
- 上传者