自动搬运

查看原文

来自洛谷，原作者为

	Into_qwq O.o

搬运于2025-08-24 22:39:43，当前版本为作者最后更新于2023-02-01 16:48:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解

异或最大，容易想到用 01 trie 来维护。

树上的一条链是容易维护的，我们令集合 $S_x$ 表示 $x$ 节点子树内的所有点，$T_x$ 表示 $x$ 节点子树外的所有点。

假设链上有两不同点 $x,y$ 且 $x$ 是 $y$ 的祖先，那么一定有 $S_x\in S_y$，所以 $T_y\in T_x$，因此我们可以对链从上往下 dfs，把所有子树外且不在 trie 中的节点权值插入 trie 中，从而动态统计答案。

观察样例，发现有很多点的答案都是整棵树中最大的异或和。

我们设任意一组构成整棵树中最大的异或和的点对为 $(x,y)$，那么所有不在 $x\to 1$ 这条链上且不在 $y \to 1$ 这条链上的节点都能以 $a_x\oplus a_y$ (即整棵树中最大的异或和) 作为答案。

那么我们就可以先求一遍整棵树最大的异或和并找到对应的 $(x,y)$，然后再求出 $x\to 1$ 和 $y\to 1$ 的答案，这样就做完了。

时间复杂度 $O(n\log A)$，空间复杂度 $O(n\log A)$。

当然可以也用压缩 trie 将空间复杂度降为 $O(n)$。

code：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int N = 5e5;

class trie {
private:
	int cnt;
	int val[N * 60], tr[N * 60][2];
public:
	void clear() {
		cnt = 0;
		memset(val, 0, sizeof(val));
		memset(tr, 0, sizeof(tr));
	}
	void ins(ll num, int id) {
		int x = 0;
		for (int i = 59; i >= 0; --i) {
			int v = (num >> i) & 1ll;
			if (!tr[x][v]) tr[x][v] = ++cnt;
			x = tr[x][v];
		}
		val[x] = id;
	}
	pair <ll, int> query(ll num) {
		int x = 0;
		ll res = 0;
		for (int i = 59; i >= 0; --i) {
			int v = (num >> i) & 1ll;
			if (!tr[x][v ^ 1]) x = tr[x][v];
			else x = tr[x][v ^ 1], res += 1ll << i;
		}
		return {res, val[x]};
	}
}T;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	vector<int> fa(n + 1);
	vector<ll> a(n + 1);
	vector<vector<int>> G(n + 1);
	for (int i = 2; i <= n; ++i){
		int x;
		cin >> x;
		G[fa[i] = x].emplace_back(i);
	}
	pair <ll, pair<int, int>> ans;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		T.ins(a[i], i);
		auto t = T.query(a[i]);
		if (t.first > ans.first)
			ans = {t.first, {t.second, i}};
	}
	T.clear();
	vector<int> p, vis(n + 1), v(n + 1);
	vector<ll> Ans(n + 1);
	ll res = 0;
	for (int x = ans.second.first; x != 1; x = fa[x])
		p.emplace_back(x);
	reverse(p.begin(), p.end());
	v[1] = 1;
	auto dfs = [&](auto dfs, int x) -> void {
		T.ins(a[x], x);
		res = max(res, T.query(a[x]).first);
		for (auto y : G[x]) {
			if (vis[y]) continue;
			vis[y] = 1;
			dfs(dfs, y);
		}
	};
	for (int x : p) {
		vis[x] = v[x] = 1;
		dfs(dfs, fa[x]);
		Ans[x] = res;
	}
	T.clear();
	p.clear();
	res = 0;
	for (int &x : vis) x = 0;
	for (int x = ans.second.second; x != 1; x = fa[x])
		p.emplace_back(x);
	reverse(p.begin(), p.end());
	for (int x : p) {
		vis[x] = v[x] = 1;
		dfs(dfs, fa[x]);
		Ans[x] = res;
	}
	for (int i = 1; i <= n; ++i)
		if (v[i]) cout << Ans[i] << '\n';
		else cout << ans.first << '\n';
}