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;
}