题解：动态树

一、题目分析

本题给定(n)个带权值的点，需要进行(m)次操作，包括询问两点间路径权值异或和、增加边、删除边、修改点权值这四种操作，要求高效处理这些动态操作。

二、解题思路

本题通过树链剖分的一种实现——LCT（Link - Cut Tree，动态树）来解决。LCT可以维护森林中树的连通性以及对路径进行各种操作。

（一）数据结构与变量定义

const int N = 100010;
int n, m;
struct Node
{
    int s[2], p, v;
    int sum, rev;
}tr[N];
int stk[N];

• N：定义点的数量的最大值。
• n：存储点的总数。
• m：存储操作的数量。
• Node结构体：用于表示LCT中的节点，包含以下成员：
  • s[2]：数组，存储左右子节点的编号，s[0]为左子节点，s[1]为右子节点。
  • p：存储父节点的编号。
  • v：存储该点的权值。
  • sum：存储以该节点为根的子树中所有点权值的异或和（包括自身）。
  • rev：懒标记，表示该子树需要进行翻转操作（因为LCT可以通过翻转操作来改变树的形态）。
• tr[N]：数组，存储LCT的所有节点信息。
• stk[N]：数组，用于辅助操作，例如在伸展（splay）操作中记录路径上的节点。

（二）辅助函数

1. 翻转标记处理函数pushrev：

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

对节点x进行翻转操作，交换其左右子树，并更新翻转标记。

1. 向上更新函数pushup：

void pushup(int x)
{
    tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}

根据子节点的信息，更新节点x的权值异或和sum。

1. 向下传递标记函数pushdown：

void pushdown(int x)
{
    if (tr[x].rev)
    {
        pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
        tr[x].rev = 0;
    }
}

将节点x的翻转标记下传给其子节点，并清除自身的翻转标记。

1. 判断是否为根节点函数isroot：

bool isroot(int x)
{
    return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}

判断节点x是否为其所在splay树的根节点。

1. 旋转函数rotate：

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if (!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
    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);
}

对节点x进行旋转操作，调整树的形态，同时更新相关节点的父节点和子节点关系，并向上更新节点的权值异或和。

1. 伸展函数splay：

void splay(int x)
{
    int top = 0, r = x;
    stk[ ++ top] = r;
    while (!isroot(r)) stk[ ++ top] = r = tr[r].p;
    while (top) pushdown(stk[top -- ]);
    while (!isroot(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y))
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}

将节点x通过旋转操作伸展到其所在splay树的根节点位置，同时处理沿途节点的翻转标记。

1. 建立路径函数access：

void access(int x)  // 建立一条从根到x的路径，同时将x变成splay的根节点
{
    int z = x;
    for (int y = 0; x; y = x, x = tr[x].p)
    {
        splay(x);
        tr[x].s[1] = y, pushup(x);
    }
    splay(z);
}

建立一条从原树的根到节点x的路径，并将节点x旋转到其所在splay树的根节点位置。

1. 将节点变为根函数makeroot：

void makeroot(int x)  // 将x变成原树的根节点
{
    access(x);
    pushrev(x);
}

将节点x变为原树的根节点，通过先建立从根到x的路径，再对x进行翻转操作实现。

1. 寻找根节点函数findroot：

int findroot(int x)  // 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
{
    access(x);
    while (tr[x].s[0]) pushdown(x), x = tr[x].s[0];
    splay(x);
    return x;
}

找到节点x所在原树的根节点，并将该根节点旋转到其所在splay树的根节点位置。

1. 分割函数split：

void split(int x, int y)  // 给x和y之间的路径建立一个splay，其根节点是y
{
    makeroot(x);
    access(y);
}

在节点x和节点y之间的路径上建立一个splay树，且该splay树的根节点为y。

1. 连接函数link：

void link(int x, int y)  // 如果x和y不连通，则加入一条x和y之间的边
{
    makeroot(x);
    if (findroot(y) != x) tr[x].p = y;
}

如果节点x和节点y不连通，则在它们之间添加一条边。

1. 切断函数cut：

void cut(int x, int y)  // 如果x和y之间存在边，则删除该边
{
    makeroot(x);
    if (findroot(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0;
        pushup(x);
    }
}

如果节点x和节点y之间存在边，则删除这条边。

（三）主函数main

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &tr[i].v);
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if (t == 0)
        {
            split(x, y);
            printf("%d\n", tr[y].sum);
        }
        else if (t == 1) link(x, y);
        else if (t == 2) cut(x, y);
        else
        {
            splay(x);
            tr[x].v = y;
            pushup(x);
        }
    }

    return 0;
}

1. 读取点的总数n和操作数量m，再读取每个点的初始权值。
2. 依次处理每个操作：
   • 若操作类型为0，调用split函数在节点x和节点y之间建立splay树，然后输出根节点y的权值异或和，即x到y路径上所有点的权值异或和。
   • 若操作类型为1，调用link函数在节点x和节点y之间添加边（若它们不连通）。
   • 若操作类型为2，调用cut函数删除节点x和节点y之间的边（若边存在）。
   • 若操作类型为3，先调用splay函数将节点x旋转到其所在splay树的根节点位置，然后修改其权值，并向上更新该节点的权值异或和。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 初始化操作：读入数据，时间复杂度为(O(n))。
• 操作处理：每次操作（连接、切断、修改权值、查询异或和）都涉及到LCT的基本操作，如splay、access等，这些操作的时间复杂度均为(O(\log n))，总共(m)次操作，所以这部分时间复杂度为(O(m\log n))。
• 总的时间复杂度为(O(n + m\log n))。

（二）空间复杂度

需要存储LCT的节点信息tr[N]以及辅助数组stk[N]，空间复杂度为(O(N + N)=O(N)) 。