首页 > 代码库 > bzoj4568 [Scoi2016]幸运数字
bzoj4568 [Scoi2016]幸运数字
Description
A 国共有 n 座城市，这些城市由 n-1 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 x 号城市，沿着 x 号城市到 y 号城市之间那条唯一的路径游览，最终从 y 城市起飞离开 A 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，游览者拍了 3 张照片，幸运值分别是 5，7，11，那么最终保留在自己身上的幸运值就是 9（5 xor 7 xor 11）。有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 5 和 11 ，可以保留的幸运值为 14 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。
Input
第一行包含 2 个正整数 n ，q，分别表示城市的数量和旅行者数量。第二行包含 n 个非负整数，其中第 i 个整数 Gi 表示 i 号城市的幸运值。随后 n-1 行，每行包含两个正整数 x ，y，表示 x 号城市和 y 号城市之间有一条道路相连。随后 q 行，每行包含两个正整数 x ，y，表示这名旅行者的旅行计划是从 x 号城市到 y 号城市。N<=20000,Q<=200000,Gi<=2^60
Output
输出需要包含 q 行，每行包含 1 个非负整数，表示这名旅行者可以保留的最大幸运值。
Sample Input
4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4
11 5 7 9
1 2
1 3
1 4
2 3
1 4
Sample Output
14
11
11
正解：树链剖分+线段树套线性基。
这题好劲啊。。$O(nlog^{4}n)$的算法还是很刚的。
这题我们是要求树上路径异或最大值，且这个异或是任意选数异或的，所以我们可以自然地想到线性基。然后我们必须要区间线性基，所以我们在外面套一个线段树。然后这题是在树上的操作，所以写树链剖分。然后这题就做完了。。
这题似乎还有个更优秀的点分治做法，复杂度只要$O(nlog^{2}n)$，似乎很优秀啊。。先填个坑吧。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define inf (1<<30) 15 #define N (20010) 16 #define ls (x<<1) 17 #define rs (x<<1|1) 18 #define il inline 19 #define RG register 20 #define ll long long 21 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 22 23 using namespace std; 24 25 struct edge{ ll nt,to; }g[2*N]; 26 struct node{ ll l,r; }q[N]; 27 28 ll head[N],top[N],fa[N],son[N],dep[N],sz[N],tid[N],pos[N],n,Q,num,cnt; 29 ll sum[4*N][62],ss[62],xx[62],a[N]; 30 31 il ll gi(){ 32 RG ll x=0,q=1; RG char ch=getchar(); 33 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 34 if (ch==‘-‘) q=-1,ch=getchar(); 35 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 36 return q*x; 37 } 38 39 il ll gll(){ 40 RG ll x=0,q=1; RG char ch=getchar(); 41 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 42 if (ch==‘-‘) q=-1,ch=getchar(); 43 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 44 return q*x; 45 } 46 47 il void insert(RG ll from,RG ll to){ g[++num]=(edge){head[from],to},head[from]=num;return; } 48 49 il void dfs1(RG ll x,RG ll p){ 50 fa[x]=p,dep[x]=dep[p]+1,sz[x]=1; RG ll v; 51 for (RG ll i=head[x];i;i=g[i].nt){ 52 v=g[i].to; if (v==p) continue; 53 dfs1(v,x); sz[x]+=sz[v]; 54 if (sz[son[x]]<=sz[v]) son[x]=v; 55 } 56 return; 57 } 58 59 il void dfs2(RG ll x,RG ll p,RG ll anc){ 60 top[x]=anc,tid[x]=++cnt,pos[cnt]=x; 61 if (son[x]) dfs2(son[x],x,anc); RG ll v; 62 for (RG ll i=head[x];i;i=g[i].nt){ 63 v=g[i].to; if (v==p || v==son[x]) continue; 64 dfs2(v,x,v); 65 } 66 return; 67 } 68 69 il void ins(ll *p,RG ll x){ 70 for (RG ll i=60;i>=0;--i) 71 if (x>>i&1){ 72 if (!p[i]){ p[i]=x; break; } 73 x^=p[i]; 74 } 75 return; 76 } 77 78 il void merge(ll *a,ll *b){ 79 for (RG ll i=60;i>=0;--i) 80 if (b[i]) ins(a,b[i]); 81 return; 82 } 83 84 il ll getmax(ll *p){ 85 RG ll res=0; 86 for (RG ll i=60;i>=0;--i) 87 if ((res^p[i])>res) res^=p[i]; 88 return res; 89 } 90 91 il void build(RG ll x,RG ll l,RG ll r){ 92 if (l==r){ ins(sum[x],a[pos[l]]); return; } 93 RG ll mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); 94 merge(sum[x],sum[ls]),merge(sum[x],sum[rs]); return; 95 } 96 97 il void query(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr){ 98 if (xl<=l && r<=xr){ merge(xx,sum[x]); return; } 99 RG ll mid=(l+r)>>1;100 if (xr<=mid) query(ls,l,mid,xl,xr);101 else if (xl>mid) query(rs,mid+1,r,xl,xr);102 else query(ls,l,mid,xl,mid),query(rs,mid+1,r,mid+1,xr);103 return;104 }105 106 il ll Query(RG ll u,RG ll v){107 RG ll ccnt=0;108 while (top[u]!=top[v]){109 if (dep[top[u]]<dep[top[v]]) swap(u,v);110 q[++ccnt].l=tid[top[u]],q[ccnt].r=tid[u];111 u=fa[top[u]];112 }113 if (dep[u]>dep[v]) swap(u,v);114 q[++ccnt].l=tid[u],q[ccnt].r=tid[v];115 memset(ss,0,sizeof(ss));116 for (RG ll i=1;i<=ccnt;++i){117 memset(xx,0,sizeof(xx));118 query(1,1,n,q[i].l,q[i].r);119 merge(ss,xx);120 }121 return getmax(ss);122 }123 124 il void work(){125 n=gi(),Q=gi(); RG ll u,v;126 for (RG ll i=1;i<=n;++i) a[i]=gll();127 for (RG ll i=1;i<n;++i){128 u=gi(),v=gi();129 insert(u,v),insert(v,u);130 }131 dfs1(1,0),dfs2(1,0,1); build(1,1,n);132 for (RG ll i=1;i<=Q;++i){133 u=gi(),v=gi();134 printf("%lld\n",Query(u,v));135 }136 return;137 }138 139 int main(){140 File("number");141 work();142 return 0;143 }
bzoj4568 [Scoi2016]幸运数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。