小圆前辈的异或树
小圆前辈去上学
https://ac.nowcoder.com/acm/contest/15332/A
小圆前辈的异或树
题目链接:https://ac.nowcoder.com/acm/contest/15332/J
题目大意:
一棵树棵树,求 。
定义:为到最短路径所经过的点的权值异或和
思路:
首先我们可以令一个根节点,处理从到的异或和,这样,我们只需要知道,和的就能求得其,但枚举肯定超时,这是就需要用到启发式合并优雅的枚举(雾
但仅仅启发式合并貌似还是不够的,因为枚举轻儿子的节点u时,我们貌似不能很快的找到对应的点,得到, 这时我们就需要建一颗字典树就能完美的解决这问题了。
时间复杂度大概就是
代码实现:
#include <iostream> #include <vector> using namespace std; const int N=1e5+7; struct Edge{int to,next;}e[2*N]; int n,a[N],pre[N],son[N],sz[N],tire[24*N][2]; vector <int> ho; int head[N],idx,tot; int flag,Ans; void add(int u,int v){ e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; } void insert(int x){ int p=0; for(int i=23;i>=0;i--){ int ch=x>>i &1; if(!tire[p][ch]) tire[p][ch]=++idx; p=tire[p][ch]; } } int qry(int x){ int p=0; int res=0; for(int i=23;i>=0;i--){ int ch=x>>i &1; if(tire[p][ch^1]){ res+=1<<i; p=tire[p][ch^1]; }else{ p=tire[p][ch^0]; } } return res; } void del(){ for(int i=0;i<=idx;i++){ tire[i][0]=0; tire[i][1]=0; } idx=0; } void add(){ for(int i=0;i<ho.size();i++){ insert(ho[i]); } ho.clear(); } void ikuzo(int u,int fa,int xo){ xo^=a[u]; pre[u]=xo; sz[u]=1; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(v==fa) continue; ikuzo(v,u,xo); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]){ son[u]=v; } } } void dfs(int u,int fa,int lca){ Ans=max(Ans,qry(pre[u]^a[lca])); ho.push_back(pre[u]); for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(v==fa) continue; dfs(v,u,lca); } } void count(int u,int fa){ Ans=max(Ans,qry(pre[u]^a[u])); insert(pre[u]); //cout<<"In "<<u<<" "<<pre[u]<<endl; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(v==fa||v==flag) continue; dfs(v,u,u); add(); } } void dsu(int u,int fa,int keep){ for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(v==fa||v==son[u]) continue; dsu(v,u,1); } if(son[u]){ dsu(son[u],u,0); flag=son[u]; } count(u,fa); flag=0; if(keep){ del(); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n-1;i++){ int u,v; scanf("%d %d",&u,&v); add(u,v),add(v,u); } ikuzo(1,-1,0); dsu(1,-1,0); printf("%d\n",Ans); }