让我们异或吧

发表于 更新于 分类于

Problem’s Website

  • 让我们异或吧

    Solution

  • 做这道题的前置知识：
    • 异或（^），位运算的一种，规则为两个数对位异或，相同为0，不同为1，即0^1=1,1^1=0,0^0=0,1^0=1
    • 异或满足交换律：a^b = b^a
    • 异或满足结合律：(a^b)^c = a^(b^c)
    • 异或自己为0：a^a = 0
    • 异或0不变：a^0 = a
  • 知道了这些，我们再来分析这道题，要求两点路径上权值的异或值，我们可以预处理一个数组，Dis[i]表示从根到i上路径的异或值，对于两个点，答案即为Dis[u]^Dis[v]，Dis[u]和Dis[v]中相同的部分(即根节点到他们的LCA)异或两次会变成0，所以这样是正确的。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    #define Maxn 100010
    using namespace std;
    int sc() {
        int xx=0,ff=1; char cch;
        while(cch<'0'|| cch>'9') {
            if(cch=='-') ff=-ff; cch=gc;
        }
        while(cch>='0'&& cch<='9') {
            xx=xx*10+(cch-48); cch=gc;
        }
        return xx*ff;
    }
    struct TREE {
        int next,to,dis;
    }edge[Maxn*2];
    int n,cnt,m;
    int head[Maxn*2],deep[Maxn],Dis[Maxn];
    namespace DY {
        void ADD(int from,int to,int dis) {
            edge[++cnt].next=head[from];
            edge[cnt].to=to;
            edge[cnt].dis=dis;
            head[from]=cnt;
        }
        void D_F(int now) {
            for(int i=head[now]; i; i=edge[i].next) {
                int to=edge[i].to;
                if(!deep[to]) {
                    deep[to]=deep[now]+1;
                    Dis[to]=Dis[now]^edge[i].dis;
                    D_F(to);
                }
            }
        }
        void main() {
            scanf("%d",&n);
            for(int i=1; i<n; i++) {
                int u,v,num;
                scanf("%d%d%d",&u,&v,&num);
                ADD(u,v,num); ADD(v,u,num);
            }
            deep[1]=1;
            D_F(1);
            scanf("%d",&m);
            while(m--) {
                int u,v;
                scanf("%d%d",&u,&v);
                printf("%d\n",Dis[u]^Dis[v]);
            }
        }
    };
    int main() {
        DY::main();
        return 0;
    }

rp++