简要题意:给定带点权树,对每个点求出其子树补中选出两个数异或得到的最大值。
考虑整个树中的最优解是 \(a_x\oplus a_y\),那么除了 \(x\) 和 \(y\) 到根的链上这些点以外,其他的所有点答案都是 \(a_x\oplus a_y\).
这样只需要考虑如何求出一条到根的链的答案。
考虑这样一条链,在 dfs 序上,子树补的范围是儿子包含父亲的。
所以每向下 dfs 一个需要求答案的点的时候,把新进入子树补范围内的点加到 01 Trie 里求答案即可。
时间复杂度 \(\mathcal{O}(n\log a)\).
#include<cstdio> #include<vector> #include<queue> #include<cstring> #include<set> #include<iostream> #include<algorithm> #include<ctime> #include<random> #include<assert.h> #define pb emplace_back #define mp make_pair #define fi first #define se second #define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'; #define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int>pii; typedef pair<ll,int>pli; typedef pair<ll,ll>pll; typedef pair<int,ll>pil; typedef vector<int>vi; typedef vector<ll>vll; typedef vector<pii>vpii; typedef vector<pil>vpil; template<typename T>T cmax(T &x, T y){return x=x>y?x:y;} template<typename T>T cmin(T &x, T y){return x=x<y?x:y;} template<typename T> T &read(T &r){ r=0;bool w=0;char ch=getchar(); while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar(); while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar(); return r=w?-r:r; } template<typename T1,typename... T2> void read(T1 &x,T2& ...y){read(x);read(y...);} const int N=500010; const int K=60; int n,fa[N],vis[N]; ll a[N],ans[N]; vi eg[N]; int tr[N*K][2],pos[N*K],tot; void add(int x,ll v,int c){ for(int i=K-1;~i;--i){ int p=(v>>i)&1; if(!tr[x][p])tr[x][p]=++tot; x=tr[x][p]; } pos[x]=c; } pli query(int x,ll v){ if(!tr[x][0]&&!tr[x][1])return mp(-1,-1); ll s=0; for(int i=K-1;~i;--i){ int p=(v>>i)&1; if(tr[x][p^1]){ s|=1ll<<i; x=tr[x][p^1]; } else x=tr[x][p]; } return mp(s,pos[x]); } void clear(){ for(int i=0;i<=tot;i++)tr[i][0]=tr[i][1]=pos[i]=0; tot=0; } ll mx; void dfs2(int x){ cmax(mx,query(0,a[x]).fi); add(0,a[x],x); for(auto v:eg[x])dfs2(v); } void dfs1(int x){ cmax(ans[x],mx); for(auto v:eg[x]){ if(!vis[v]){ dfs2(v); } } cmax(mx,query(0,a[x]).fi); add(0,a[x],x); for(auto v:eg[x])if(vis[v])dfs1(v); } void solve(int x){ while(x)vis[x]=1,x=fa[x]; mx=0;clear(); dfs1(1); for(int i=1;i<=n;i++)vis[i]=0; } signed main(){ read(n); for(int i=1;i<n;i++){ read(fa[i+1]); eg[fa[i+1]].pb(i+1); } for(int i=1;i<=n;i++)read(a[i]); ll mx=0;pii po; for(int i=1;i<=n;i++){ if(i>1){ auto tmp=query(0,a[i]); if(tmp.fi>mx){ mx=tmp.fi; po=mp(tmp.se,i); } } add(0,a[i],i); } clear(); int x=po.fi,y=po.se; while(x)vis[x]=1,x=fa[x]; while(y)vis[y]=1,y=fa[y]; for(int i=1;i<=n;i++) if(!vis[i])ans[i]=mx; else vis[i]=0; solve(po.fi); solve(po.se); for(int i=1;i<=n;i++)cout << ans[i] << '\n'; return 0; }