1.78KB 狂砍 20 分球调
查看原帖
1.78KB 狂砍 20 分球调
675466
zzx0102楼主2023/8/24 08:31
#include<bits/stdc++.h>
using namespace std;
#define mk_p make_pair
#define ll long long
const int N = 500010, M = N * 62;
int n, fa[N], g[N]; vector<int> e[N];
ll nowans, w[N], ans[N];
struct Trie01 {
	int ls[M], rs[M], idx;
	void init() {
		for(int i = 1; i <= n; i++) g[i] = 0;
		for(int i = 0; i <= idx; i++) ls[i] = rs[i] = 0;
		idx = nowans = 0;
	}
	void ins(ll x) {
		int rt = 0;
		for(int i = 61; i >= 0; i--) {
			if(x & (1 << i)) {
				if(!ls[rt]) ls[rt] = ++idx;
				rt = ls[rt];
			}
			else {
				if(!rs[rt]) rs[rt] = ++idx;
				rt = rs[rt];
			}
		}
	}
	int ask(ll x) {
		int rt = 0; ll ans = 0;
		for(int i = 61; i >= 0; i--) {
			if(x & (1 << i)) {
				if(rs[rt]) rt = rs[rt], ans |= (1 << i);
				else rt = ls[rt];
			}
			else {
				if(ls[rt]) rt = ls[rt], ans |= (1 << i);
				else rt = rs[rt];
			}
		}
		nowans = max(nowans, ans);
		return ans;
	}
} T;
void dfs(int u, int fa) {
	T.ins(w[u]); T.ask(w[u]);
	for(int v: e[u]) {
		if(v != g[u] && v != fa) {
			dfs(v, u);
		}
	}
}
void solve(int u) {
	for(int i = u; i != 1; i = fa[i]) g[fa[i]] = i;
	nowans = 0;
	for(int i = 1; i != u; i = g[i]) ans[i] = nowans, dfs(i, fa[i]);
	ans[u] = nowans;
}
signed main() {
	ios::sync_with_stdio(0); cin >> n; for(int i = 2; i <= n; i++) {cin >> fa[i]; e[fa[i]].push_back(i);}
	for(int i = 1; i <= n; i++) {cin >> w[i]; T.ins(w[i]);} int x = 0, y = 0, A = 0; memset(ans, -1, sizeof ans);
	for(int i = 1; i <= n; i++) {int now = T.ask(w[i]); if(now > A) A = now, x = w[i], y = now ^ w[i];}
	for(int i = 1; i <= n; i++) ans[i] = A;
	int X = 0, Y = 0; for(int i = 1; i <= n; i++) {if(w[i] == x) X = i; else if(w[i] == y) Y = i;}
	T.init(); solve(X); T.init(); solve(Y); for(int i = 1; i <= n; i++) cout << (ans[i] >= 0 ? ans[i] : A) << '\n';
	return 0;
}
2023/8/24 08:31
加载中...