自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:15:27，当前版本为作者最后更新于2020-01-07 18:30:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

长链剖分的经典应用。

显然这个问题有 $\mathcal O(n \log n) - \mathcal O(\log n)$ 的树上倍增做法，然而还不够优秀。

首先我们进行预处理：

1. 对树进行长链剖分，记录每个点所在链的顶点和深度，$\mathcal O(n)$。
2. 树上倍增求出每个点的 $2^n$ 级祖先，$\mathcal O(n \log n)$。
3. 对于每条链，如果其长度为 $len$，那么在顶点处记录顶点向上的 $len$ 个祖先和向下的 $len$ 个链上的儿子，$\mathcal O(n)$。
4. 对 $i \in [1, n]$ 求出在二进制下的最高位 $h_i$，$\mathcal O(n)$。

对于每次询问 $x$ 的 $k$ 级祖先：

1. 利用倍增数组先将 $x$ 跳到 $x$ 的 $2^{h_k}$ 级祖先，设剩下还有 $k^{\prime}$ 级，显然 $k^{\prime} < 2^{h_k}$，因此此时 $x$ 所在的长链长度一定 $\ge 2^{h_k} > k^{\prime}$。
2. 由于长链长度 $> k^{\prime}$，因此可以先将 $x$ 跳到 $x$ 所在链的顶点，若之后剩下的级数为正，则利用向上的数组求出答案，否则利用向下的数组求出答案。

这样时间复杂度为 $\mathcal O(n \log n) - \mathcal O(1)$ 的。

const int N = 5e5 + 7;
int n, q, rt, g[N], d[N], f[N][21], son[N], dep[N], top[N], ans;
vi e[N], u[N], v[N];
ui s;
ll Ans;

inline ui get(ui x) {
	return x ^= x << 13, x ^= x >> 17, x ^= x << 5, s = x; 
}

void dfs(int x) {
	dep[x] = d[x] = d[f[x][0]] + 1;
	for (auto y : e[x]) {
		f[y][0] = x;
		for (int i = 0; f[y][i]; i++) f[y][i+1] = f[f[y][i]][i];
		dfs(y);
		if (dep[y] > dep[x]) dep[x] = dep[y], son[x] = y;
	}
}

void dfs(int x, int p) {
	top[x] = p;
	if (x == p) {
		for (int i = 0, o = x; i <= dep[x] - d[x]; i++)
			u[x].pb(o), o = f[o][0];
		for (int i = 0, o = x; i <= dep[x] - d[x]; i++)
			v[x].pb(o), o = son[o];
	}
	if (son[x]) dfs(son[x], p);
	for (auto y : e[x]) if (y != son[x]) dfs(y, y);
}

inline int ask(int x, int k) {
	if (!k) return x;
	x = f[x][g[k]], k -= 1 << g[k], k -= d[x] - d[top[x]], x = top[x];
	return k >= 0 ? u[x][k] : v[x][-k];
}

int main() {
	rd(n), rd(q), rd(s), g[0] = -1;
	for (int i = 1; i <= n; i++)
		rd(f[i][0]), e[f[i][0]].pb(i), g[i] = g[i>>1] + 1;
	rt = e[0][0], dfs(rt), dfs(rt, rt);
	for (int i = 1, x, k; i <= q; i++) {
		x = (get(s) ^ ans) % n + 1;
		k = (get(s) ^ ans) % d[x];
		Ans ^= 1ll * i * (ans = ask(x, k));
	}
	print(Ans);
	return 0;
}