首页 > 代码库 > HDU4757 Tree(可持久化Trie)
HDU4757 Tree(可持久化Trie)
写过可持久化线段树，但是从来没写过可持久化的Trie，今天补一补。
题目就是典型的给你一个数x，和一个数集，问x和里面的某个数xor起来的最大值是多少。
最原始的是数集是固定的，只需要对数集按照高到低位去建Trie,然后贪心匹配就可以了。
这里则是对树上路径的操作，其实也是一样的，对每个节点x维护root到x的Trie,然后纪录下往左走往右走的叶子节点个数，设z=lca(x,y),那么到了个某个节点能否往某个儿子走的限制条件是 sz[ch[x][c]]+sz[ch[y][c]]-2*sz[ch[z][c]]>0，这样说明下面是存在c的儿子的，接着往下走即可。当然这样算其实是会漏掉lca的，所以最后还要和lca取最大值。
区间的询问作为这题的特例同理也是可以处理的。
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cmath>#include <queue>#include <cassert>#include <vector>#include <set>using namespace std;#define maxn 120000#define maxnode 2200000#define maxlogv 16vector<int> G[maxn];int n,m;int a[maxn];int f[maxlogv+2][maxn];int dep[maxn];int ch[maxnode][2];int sz[maxnode];int tot;int root[maxn];int newnode(){ memset(ch[tot],0,sizeof(ch[tot])); sz[tot]=0; return tot++;}// insert val for x with father as yvoid insert(int x,int y,int val){ x=root[x];y=root[y]; for(int i=15;i>=0;--i){ int c=(val>>i)&1; if(!ch[x][c]){ int id=newnode(); ch[x][c]=id; ch[x][!c]=ch[y][!c]; sz[ch[x][c]]=sz[ch[y][c]]; } x=ch[x][c],y=ch[y][c]; ++sz[x]; }}void dfs(int u,int fa){ f[0][u]=fa;dep[u]=dep[fa]+1; root[u]=newnode(); insert(u,fa,a[u]); for(int i=0;i<G[u].size();++i){ int v=G[u][i]; if(v==fa) continue; dfs(v,u); }}int lca(int u,int v){ if(dep[u]>dep[v]) swap(u,v); for(int k=0;k<maxlogv;++k){ if( (dep[v]-dep[u])>>k&1){ v=f[k][v]; } } if(u==v) return u; for(int k=maxlogv-1;k>=0;--k){ if(f[k][u]!=f[k][v]){ u=f[k][u]; v=f[k][v]; } } return f[0][u];}int query(int x,int y,int val){ int z=lca(x,y);int res=a[z]^val; x=root[x],y=root[y],z=root[z]; int ret=0; for(int i=15;i>=0;--i){ int c=(val>>i)&1; if(sz[ch[x][!c]]+sz[ch[y][!c]]-2*sz[ch[z][!c]]>0){ ret+=1<<i; c=!c; } x=ch[x][c]; y=ch[y][c]; z=ch[z][c]; } return max(ret,res);}int main(){ while(cin>>n>>m){ for(int i=1;i<=n;++i){ scanf("%d",a+i); G[i].clear(); } int ui,vi; for(int i=0;i<n-1;++i){ scanf("%d%d",&ui,&vi); G[ui].push_back(vi); G[vi].push_back(ui); } memset(root,0,sizeof(root)); tot=1; memset(f,0,sizeof(f)); memset(sz,0,sizeof(sz)); dep[0]=0; dfs(1,0); for(int k=0;k+1<maxlogv;++k){ for(int v=1;v<=n;++v){ if(f[k][v]==0) f[k+1][v]=0; else f[k+1][v]=f[k][f[k][v]]; } } int xi,yi,zi; for(int i=0;i<m;++i){ scanf("%d%d%d",&xi,&yi,&zi); printf("%d\n",query(xi,yi,zi)); } } return 0;}
HDU4757 Tree(可持久化Trie)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。