异或是一种神奇的运算,大部分人把它总结成不进位加法.
在生活中…xor运算也很常见。比如，对于一个问题的回答，是为1，否为0.那么：
（A是否是男生 ）xor（ B是否是男生）＝A和B是否能够成为情侣
好了，现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树，它很高兴自己有N个结点。树的每条边上有一个权值。我们要进行M次询问，对于每次询问，我们想知道某两点之间的路径上所有边权的异或值。
输入格式：
输入文件第一行包含一个整数N，表示这颗开心的树拥有的结点数，以下有N-1行，描述这些边，每行有3个数，u,v,w,表示u和v之间有一条权值为w的边。接下来一行有一个整数M，表示询问数。之后的M行，每行两个数u,v，表示询问这两个点之间的路径上的权值异或值。
输出格式：
输出M行，每行一个整数，表示异或值
对于40%的数据，有1 ≤ N，M ≤ 3000；
对于100%的数据，有1 ≤ N ，M≤ 100000。
第一眼看到这题，想求lca再跑spfa（这不是sb嘛）
然后当然这是不对的
稍微想一下
先预处理出每个点到根节点的异或和,用dis数组保存
运用异或运算的性质
x^y^y=x
假设我们要求的这两点的lca为c
dis[u]=dis[c]^dis[c-u];
现在要求dis[c-u]
用上面的性质
dis[c-u]=dis[u]^dis[c];(因为dis[u]=dis[c]^dis[c-u])
再把lca两端的异或和异或掉，就OK了
贴代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; inline int read(){ int x=0; bool f=1; char c=getchar(); while(!isdigit(c)){if(c=='-')f=0;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} if(!f)return 0-x; return x; } const int M=1000100; int n,m,cnt,head[M],depth[M],f[M][20],dis[M],vis[M],QAQ,lg[M]; struct data{ int to,dis,next; }e[M]; void add(int u,int v,int w){ e[++cnt].to=v; e[cnt].dis=w; e[cnt].next=head[u]; head[u]=cnt; } inline void pre(int u,int sum){ vis[u]=1; dis[u]=sum; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(!vis[v]){ pre(v,sum^e[i].dis); } } } inline void dfs(int u,int fa){ depth[u]=depth[fa]+1; f[u][0]=fa; for(int i=1;(1<<i)<=depth[u];i++){ f[u][i]=f[f[u][i-1]][i-1]; } for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(v==fa)continue; dfs(v,u); } } inline int lca(int a,int b){ if(depth[a]<depth[b])swap(a,b); while(depth[a]>depth[b]){ a=f[a][lg[depth[a]-depth[b]]-1]; } if(a==b)return a; for(int i=lg[depth[a]]-1;i>=0;i--){ if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i]; } return f[a][0]; } int main(){ // freopen("haha.in","r",stdin); n=read(); for(int i=1;i<n;i++){ int x,y,z; x=read(),y=read(),z=read(); add(x,y,z); add(y,x,z); } for(int i=1;i<=n;i++){ lg[i]=lg[i-1]+(1<<lg[i-1]==i); } pre(1,0); dfs(1,0); m=read(); for(int i=1;i<=m;i++){ int x,y; x=read(),y=read(); int l=lca(x,y); printf("%d\n",(dis[x]^dis[l])^(dis[y]^dis[l])); } // fclose(stdin); return QAQ; }
转载于:https://www.cnblogs.com/djhsbdb/p/9868845.html
相关资源：数据结构—成绩单生成器