动态树的异或和

一 问题描述

给定 n 个节点及每个节点的权值，节点编号为 1～n ，处理 m 种操作。操作格式：

① 0 x y ，查询 x 到y 路径上点的权值的 xor 和，保证 x 到 y 是连通的。

② 1 x y ，连接 x 到 y ，若 x 到 y 已经连通，则无须连接。

③ 2 x y ，删除边(x , y)，不保证边 (x , y ) 存在。

④ 3 x y ，将节点x 的权值变成y 。

二 输入和输出

1 输入

第 1 行包含两个整数 n 和 m ，表示节点数和操作数，1≤n≤10^5 ，1≤m≤3×10^5 ；接下来的 n 行，每行都包含一个 [1, 10^9 ]的整数，代表节点的权值；最后的 m 行，每行都包含 3 个整数，表示一种操作。

2 输出

对每个查询操作，都单行输出一个整数，表示 x 到 y 路径上点权的 xor 和。

三 输入和输出样例

1 输入样例

3 3

1

2

3

1 1 2

0 1 2

0 1 1

2 输出样例

3

1

四 分析

本问题为典型的动态树基本操作，包括路径上的权值 xor、连边、删边、点更新。

五 算法设计

0 x y ：询问 x 到 y 路径上点的权值的 xor 和。首先切分 x -y 路径，然后返回树根 y 的 v 值即可（在旋转过程中更新 xor）。

1 x y ：连接 x、y 。先判断 x 、y 的连通性，若不连通，则连接 x 、y 。若 x 到 y 已经连通，则无须连接。

2 x y ：删除边 (x , y )。先判断 x 、y 的连通性，若连通且 x、y 之间有边，则删除 x 、y 之间的边。

3 x y ：将节点 x 的权值变成 y 。将 x 旋转到树根，然后令a[x ]=y 。

六 代码

package com.platform.modules.alg.alglib.p3690;
 
public class P3690 {
    private int MAXN = 300005;
    int n, m;
    int a[] = new int[MAXN];
 
    int top;
    int c[][] = new int[MAXN][2];
    int fa[] = new int[MAXN];
    int v[] = new int[MAXN];
    int st[] = new int[MAXN];
    int rev[] = new int[MAXN];
 
    public String output = "";
 
    // 更新当前节点的值（路径上点值 XOR ）
    void update(int x) {
        v[x] = v[c[x][0]] ^ v[c[x][1]] ^ a[x];
    }
 
    // 下传懒惰标记
    void pushdown(int x) {
        if (rev[x] == 1) {
            rev[c[x][0]] ^= 1;
            rev[c[x][1]] ^= 1;
            rev[x] ^= 1;
            int temp = c[x][0];
            c[x][0] = c[x][1];
            c[x][1] = temp;
        }
    }
 
    // 判断是否是所在 Splay 的根节点
    boolean isroot(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }
 
    // 旋转，将x变成y的父节点
    void rotate(int x) {
        int y = fa[x], z = fa[y], k;
        if (c[y][0] == x) {
            k = 1;
        } else {
            k = 0;
        }
        // 如果 y 不是根节点，那么将 z 的儿子 y 变成 x
        if (!isroot(y)) c[z][c[z][1] == y ? 1 : 0] = x;
        fa[x] = z;
        fa[y] = x;
        fa[c[x][k]] = y;
        c[y][k == 0 ? 1 : 0] = c[x][k];
        c[x][k] = y;
        update(y);
        update(x);
    }
 
    void splay(int x) {
        st[top = 1] = x;
        for (int i = x; !isroot(i); i = fa[i]) st[++top] = fa[i];//一定要从上往下
        while (top > 0) pushdown(st[top--]);
        while (!isroot(x)) {//将x旋到根
            int y = fa[x], z = fa[y];
            if (!isroot(y)) {
                if (c[y][0] == x ^ c[z][0] == y) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
    }
 
    // 连接一条 x 到根的实链
    void access(int x) {
        for (int y = 0; x > 0; x = fa[y = x]) {
            splay(x);
            c[x][1] = y;
            update(x);
        }
    }
 
    // 换根，将x变成原树的根
    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }
 
    // 找 x 的根节点
    int findroot(int x) {
        access(x);
        splay(x);
        while (c[x][0] > 0) x = c[x][0];
        return x;
    }
 
    // 拉出一条 x 到 y 的路径为一个 Splay
    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }
 
    // 删除一条 x 到 y 的边
    void cut(int x, int y) {
        split(x, y);
        if (c[y][0] != x || c[x][1] > 0) return; // 坑点，此时 x 是 y 的左儿子，且 x 没有右儿子，如果有说明x--y中间有节点
        c[y][0] = fa[c[y][0]] = 0;
        update(y);
    }
 
    // 连一条 x 到 y 的虚边
    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }
 
    public String cal(String input) {
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        m = Integer.parseInt(word[1]);
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(line[i]);
            v[i] = a[i];
        }
        int count = 1;
        while (m-- > 0) {
            int opt, x, y;
            String[] query = line[n + count++].split(" ");
            opt = Integer.parseInt(query[0]);
            x = Integer.parseInt(query[1]);
            y = Integer.parseInt(query[2]);
 
            if (opt == 0) {
                split(x, y);
                output += v[y] + "\n";
            } else if (opt == 1) {
                if (findroot(x) != findroot(y)) // 不连通
                    link(x, y);
            } else if (opt == 2) {
                if (findroot(x) == findroot(y)) // 连通
                    cut(x, y);
            } else if (opt == 3) {
                splay(x);
                a[x] = y;
            }
        }
        return output;
    }
}

七 测试