题解 LuoGu P2420 让我们异或吧

作者: MayFlyyh 分类: LCA 发布时间: 2018-03-17 21:23 ė 6 没有评论

LuoGu P2420 让我们异或吧

题目描述

异或是一种神奇的运算,大部分人把它总结成不进位加法.

在生活中…xor运算也很常见。比如,对于一个问题的回答,是为1,否为0.那么:

好了,现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树,它很高兴自己有N个结点。树的每条边上有一个权值。我们要进行M次询问,对于每次询问,我们想知道某两点之间的路径上所有边权的异或值。

输入格式:
输入文件第一行包含一个整数N,表示这颗开心的树拥有的结点数,以下有N-1行,描述这些边,每行有3个数,u,v,w,表示u和v之间有一条权值为w的边。接下来一行有一个整数M,表示询问数。之后的M行,每行两个数u,v,表示询问这两个点之间的路径上的权值异或值。

输出格式:
输出M行,每行一个整数,表示异或值


题意简单,探讨一下xor的交换律

(a xor b) xor c == a xor (b xor c) == (a xor c) xor b

0 xor V == V

我们通过倍增的思想来维护,该点与父亲(第1代祖先),爷爷(第2代祖先)………以及第N代祖先路上的边的xor值

对于两个点,我们找到这两个点的最近公共祖先lca

只用求出两个点到lca的xor值,再将这两个值xor一下即为答案

代码:


\#include<bits/stdc++.h> int last[100010],D[100010]; int v[100010]; int F[100010][30]; int o[100010][30],cnt; int log2n,n; struct edge{ int to,next,v; }e[200100]; inline void add(int x,int y,int z){ e[++cnt].next=last[x],last[x]=cnt; e[cnt].to=y,e[cnt].v=z; } inline int dfs(int x,int fa){ D[x]=D[fa]+1; F[x][0]=fa; v[x]=1; for(int i=last[x];i;i=e[i].next){ if(!v[e[i].to]) dfs(e[i].to,x); o[e[i].to][0]=e[i].v; } } inline int BZ(){ for(int i=1;i<=log2n;++i) for(int j=0;j<=n;++j){ if(D[j]>=(1<<i)){ F[j][i]=F[F[j][i-1]][i-1]; } } for(int i=1;i<=log2n;++i) for(int j=0;j<=n;++j){ if(D[j]>=(1<<i)){ o[j][i]=o[F[j][i-1]][i-1]^o[j][i-1]; } } } inline int LCA(int x,int y){ if(D[x]<D[y]) std::swap(x,y); for(int i=log2n;i>=0;--i) if(D[F[x][i]]>D[y]) x=F[x][i]; if(x==y) return x; for(int i=log2n;i>=0;--i){ if(F[x][i]!=F[y][i]) x=F[x][i],y=F[y][i]; } return F[x][0]; } inline int ask(int x,int y){ if(D[x]<D[y]) std::swap(x,y); int ans=0; for(int i=log2n;i>=0;--i) if(D[F[x][i]]>=D[y]){ ans^=o[x][i]; x=F[x][i]; } if(x==y) return ans; for(int i=log2n;i>=0;--i){ if(F[x][i]!=F[y][i]){ ans^=o[x][i]; ans^=o[y][i]; x=F[x][i],y=F[y][i]; } } ans^=o[x][0]; ans^=o[y][0]; return ans; } int main (){ scanf("%d",&n); for(int i=1;i<=n-1;++i){ int x,y,z; scanf("%d %d %d",&x,&y,&z); add(x,y,z); add(y,x,z); } log2n=log(n*1.0)/log(2.0)*1.0+0.5; dfs(1,0); BZ(); int m; scanf("%d",&m); for(int i=1;i<=m;++i){ int x,y; scanf("%d %d",&x,&y); printf("%d\n",ask(x,y)); } return 0; }

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/178

0

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部