trie 树简单题 RE 60pts 求调
查看原帖
trie 树简单题 RE 60pts 求调
775991
jianamisabina楼主2025/7/24 13:45
#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <vector>
#define int long long

using namespace std;
               
const int N = 5e5 + 10;

int n,f[N],a[N],cnt,ans[N],sonlist[N],now;
  signed  trie[500000 * 61][2],val[500000 * 61];
vector <int> G[N];

void in(int pos){
	int tmp[128] = {0},tot = 0;
	int t = a[pos];
	for(int i = 1;i <= 60;i ++){
		tmp[i] = t & 1;
		t >>= 1;
	}
	reverse(tmp + 1,tmp + 61);
	int f = 0;
	for(int i = 1;i <= 60;i ++){
		int e = tmp[i];
		if(!trie[f][e]){
			trie[f][e] = ++cnt;
		}
		f = trie[f][e];
	}val[f] = pos;
}

int query(int pos){
	int tmp[128] = {0},tot = 0;
	int t = a[pos];
	for(int i = 1;i <= 60;i ++){
		tmp[i] = t & 1;
		t >>= 1;
	}
	reverse(tmp + 1,tmp + 61);
	int f = 0;
	for(int i = 1;i <= 60;i ++){
		int e = tmp[i];
		if(trie[f][e ^ 1]){
			f = trie[f][e ^ 1];
		}else f = trie[f][e];
	}
	return val[f];	
}

void dfsin(int u){
    if(u == 0) return;
	in(u);now = max(now,(a[u] ^ a[query(u)]));
	for(auto v : G[u]){
		dfsin(v);
	}
}

void deal(int x){
	int tot = 0;
	while(x){
        //cout << x << ' ';
		sonlist[++tot] = x;
		x = f[x];     
	}
    //cout << tot << '\n';
    //return;
	memset(trie,0,sizeof(trie));
    memset(val,0,sizeof(val));
    now = 0;
	for(int i = tot;i >= 1;i --){
		int s = sonlist[i];
		ans[s] = now;
		if(i == 1) break;
		for(auto j : G[s]){
			if(j != sonlist[i - 1]) dfsin(j);
		}
        in(s);now = max(now,(a[s] ^ a[query(s)]));
        
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    cin >> n;
    for(int i = 2;i <= n;i ++){
    	cin >> f[i];
    	G[f[i]].push_back(i);
	}
	
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		in(i);a
	} 
	int mx = 0,x = 0,y = 0;
	for(int i = 1;i <= n;i ++){
		int tmp = query(i);
		if((a[tmp] ^ a[i]) > mx){
			mx = (a[tmp] ^ a[i]);
			x = tmp;y = i;
		}
	}//return 0;
    //cout << x << ' ' <<  y << '\n';return 0;
	deal(x);deal(y);
	
	ans[1] = -1;
	if(G[1].size() == 1) ans[G[1][0]] = -1;
	
	for(int i = 1;i <= n;i ++){
        if(ans[i] == -1) cout << 0 << '\n';
        else if(ans[i]) cout << ans[i] << '\n';
        else cout << mx << '\n';
    } 
	return 0;
}

2025/7/24 13:45
加载中...