动态树问题

解题思路

本题是动态树的一个模板题，这里用 $Link\_Cut\_Tree$ 版的动态树来做。

对于操作一，我们只需要进行一次 $split(x, y)$ 操作，然后查询一下所在 $Splay$ 的根节点信息即可，对于每个节点需要记录一下维护区间的异或和 $sum$

对于操作二，其实就是一次 $link(x, y)$ 操作

对于操作三，其实就是一次 $cut(x,y)$ 操作

对于操作四，只需要将 $x$ 转到所在 $Splay$ 的根节点，此时 $x$ 的值的变化不会对其他子节点的值造成影响，直接修改然后进行一次 $pushup(x)$ 即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

struct Node
{
    int s[2], p, v; //子节点、父节点、权值
    int sum, rev; //权值和、记录子节点是否需要翻转（懒标记）
}tr[N]; //Splay
int stk[N]; //辅助栈，用于下传懒标记

int n, m;

void pushrev(int x) //将 x 翻转
{
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].rev ^= 1;
}

void pushup(int x) //用子节点的信息更新当前节点的信息
{
    tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}

void pushdown(int x) //将当前节点的懒标记下传
{
    if(tr[x].rev)
    {
        pushrev(tr[x].s[0]), pushrev(tr[x].s[1]); //将左、右儿子分别翻转
        tr[x].rev = 0; //将当前节点的懒标记清空
    }
}

bool is_root(int x) //判断当前节点是不是根节点
{
    //若当前节点的父节点的左、右儿子都不是当前节点，说明当前节点是根节点
    return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}

void rotate(int x) //左旋、右旋
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if(!is_root(y)) tr[z].s[tr[z].s[1] == y] = x; //y 是根节点时不能修改父节点的信息，会导致实边更改
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x) //将 x 转到所在 Splay 的根节点
{
    //在将 x 转上去之前，先将根节点到 x 的所有懒标记传下去
    int top = 0, r = x;
    stk[++top] = r;
    while(!is_root(r)) stk[++top] = r = tr[r].p;
    while(top) pushdown(stk[top--]);

    //将 x 转到根节点
    while(!is_root(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if(!is_root(y))
        {
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}

void access(int x) //建立一条从 x 到根节点的实边路径，同时将 x 转到所在 Splay 的根节点
{
    int z = x;
    //y 表示当前实边路径的根节点，x 所在的实边路径为当前要合并的实边路径
    for(int y = 0; x; y = x, x = tr[x].p)
    {
        splay(x); //将 x 转到所在 Splay 的根节点
        tr[x].s[1] = y, pushup(x); //将 y 插入 x 的右子树
    }
    splay(z);
}

void make_root(int x) //将 x 变成整棵树的根节点，同时将 x 转到所在 Splay 的根节点
{
    access(x); //建立一条从 x 到根节点的实边路径，同时将 x 转到所在 Splay 的根节点
    pushrev(x); //然后将整棵子树翻转
}

int find_root(int x) //找到 x 所在实边路径的根节点，再将 x 所在实边路径的根节点变成整棵树的根节点
{
    access(x); //建立一条从 x 到根节点的实边路径，同时将 x 转到所在 Splay 的根节点
    while(tr[x].s[0]) pushdown(x), x = tr[x].s[0]; //向左走到底（递归之前一定要下传懒标记）
    splay(x); //将当前的 x 转到所在 Splay 的根节点
    return x;
}

void split(int x, int y) //建立一条从 x 到 y 的实边路径，实边路径对应的 Splay 的根节点是 y
{
    make_root(x); //将 x 变成整棵树的根节点，同时将 x 转到所在 Splay 的根节点
    access(y); //建立一条从 x 到根节点的实边路径，同时将 x 转到所在 Splay 的根节点
}

void link(int x, int y) //如果 x 和 y 不连通，则加入一条 x 和 y 中间的边（虚边）
{
    make_root(x); //将 x 变成整棵树的根节点，同时将 x 转到所在 Splay 的根节点
    if(find_root(y) != x) tr[x].p = y; //如果 x 和 y 不连通，建立虚边
}

void cut(int x, int y) //如果 x 和 y 之间存在边，则删除该边
{
    make_root(x); //将 x 变成整棵树的根节点，同时将 x 转到所在 Splay 的根节点
    //如果 x 和 y 连通，y 是 x 走右子节点且 y 不存在左子树，说明 x 和 y 之间存在边
    if(find_root(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0; //将边删去
        pushup(x); //更新 x 的信息
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++) scanf("%d", &tr[i].v);

    while(m--)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 0) //查询 x 到 y 的路径上所有点的异或和
        {
            split(x, y); //建立一条从 x 到 y 的实边路径
            printf("%d\n", tr[y].sum); //split 后 y 是所在 Splay 的根节点
        }
        else if(op == 1) link(x, y); //在 x 和 y 之间添加一条边
        else if(op == 2) cut(x, y);//将 x 和 y 之间的边删去
        else //将 x 的权值改为 y
        {
            splay(x); //将 x 转到所在 Splay 的根节点
            tr[x].v = y; //将 x 的权值修改为 y
            pushup(x); //更新 x 的信息
        }
    }
    return 0;
}