问题描述:
给定 n 个点（编号为 1 ~ n）以及每个点的权值，处理接下来的 m 个操作。操作有以下 4 种，操作编号为0 ~ 3。
0 x y 代表查询从 x 到 y 的路径上的点的权值的异或和。保证 x 到 y 是联通的。
1 x y 代表加边,加x到y的边,若 x 到 y 已经联通，则无须连接。
2 x y 代表删除边（x，y）,不保证边（x，y）存在。
3 x y 代表将点 x上的权值变成 y。
| 输入：第 1 行输入两个整数 n 和 m ，代表点数和操作数。接下来 n 行中，每行输入一个整数，第 i + 1 行的整数 ai，表示节点i的权值。接下来 m 行中，每行输入 3 个整数，分别代表操作类型和操作所需的量。 |
| 输出：对每个 0 号操作，输出一个整数，表示 x 到 y 的路径上点权的异或和。 |
| 数据范围：1 ≤ n ≤ 105，1 ≤ m ≤ 3 x 105，1 ≤ ai ≤ 109，对于操作 0 ~ 2，保证 1 < x，y ≤ n。对于操作 3，保证 1 ≤ x ≤ n，1 ≤ y ≤ 109 |
| 输入样例 | 输出样例 |
| 3 3 1 2 3 1 1 2 0 1 2 0 1 1 | 3 1 |
| 5 14 114 514 19 19 810 1 1 2 0 1 2 2 1 2 1 1 2 1 2 3 2 1 3 1 1 3 1 4 5 1 2 5 0 3 5 0 3 4 3 5 233333 0 1 5 0 2 5 | 624 315 296 232709 232823 |
模板题
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
/* fa表示父节点的索引。
* ch[2]表示左右子节点的索引。
* sum表示从根节点到当前节点路径上的异或和。
* val表示当前节点的值。
* lazy用于标记是否需要对当前节点及其子树进行翻转操作。*/
struct node{ int fa,ch[2],sum,val,lazy; }t[N];
#define lc t[x].ch[0] //左儿子
#define rc t[x].ch[1] //右儿子
bool isRoot(int x){ //判断是否是splay根节点
int g=t[x].fa; //通过检查节点x在其父节点g中的位置
return t[g].ch[0]!=x && t[g].ch[1]!=x; //若为根,则父结点不应该有这个儿子
}
void pushup(int x){ //维护从根节点到节点x路径上的异或和，题目要求
t[x].sum=t[x].val^t[lc].sum^t[rc].sum; //更新节点x的sum值，使其等于节点x自身值与左右子节点sum值的异或运算结果。
}
void reverse(int x){ //翻转节点x的左右子树，并更新lazy标记
if(!x)return;
swap(lc,rc); //翻转x的左右儿子
t[x].lazy^=1; //懒惰标记，先不翻转儿子的后代，后面再翻转
}
void pushdown(int x){ //递归翻转x的儿子的后代，并释放懒标记。
if(t[x].lazy){ //若节点x的lazy标记位为1，表明节点的子树需要进行翻转。
reverse(lc); //函数递归地对节点x的左右子节点进行翻转
reverse(rc);
t[x].lazy=0; //清零节点x的lazy标记位，表示已处理完翻转操作
}
}
void push(int x){ //将节点x及其祖先节点的lazy标记传递到根节点，并更新lazy标记
if(!isRoot(x)) push(t[x].fa); //从根到x全部pushdown
pushdown(x);//
}
void rotate(int x){ //节点的旋转操作，保持二叉树的平衡
int y=t[x].fa; //获取当前节点x的父节点y,和父节点y的父节点z
int z=t[y].fa;
int k=t[y].ch[1]==x; //确定节点x是在父节点y的左子树还是右子树
if(!isRoot(y)) t[z].ch[t[z].ch[1]==y]=x; //如果节点y不是根节点，则更新节点z的子节点指向
t[x].fa=z; //更新节点x的父节点为节点z，（认父不认子）
t[y].ch[k]=t[x].ch[k^1]; //更新节点y的子节点，k^1表示取反，x的子节点赋值给y的子节点
if( t[x].ch[k^1] ) t[ t[x].ch[k^1] ].fa = y; //如果节点x的k子节点存在，k子节点的父节点设为y
t[y].fa=x; //更新节点y的父节点为节点x
t[x].ch[k^1]=y; //更新节点x的子节点，完成旋转
pushup(y); //更新旋转后节点y的值，保持树的属性
}
void splay(int x){ //将节点x旋转为它所在的Splay树的根节点
int y,z;
push(x); //处理x的所有子孙的lazy标记
while(!isRoot(x)){ //在循环中不断进行旋转操作，直至节点x成为Splay树的根节点
y=t[x].fa,z=t[y].fa; //获取节点x的父节点y，和父节点y的父节点z
if(!isRoot(y)) //如果节点y不是根节点，则执行旋转操作
(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y); //如果节点y是z的左儿子，则执行左旋操作，否则执行右旋操作
rotate(x);
}
pushup(x); //更新节点x的sum值
}
void access(int x){ //从x往上走，沿着虚边走到根，过程中通过splay将访问的节点旋转到根节点，并建立实链
for(int child=0; x; child=x, x=t[x].fa){ //从节点x开始，沿父节点向上遍历至根节点
splay(x); //将节点x旋转到根节点
rc = child; //将右孩子设置为child，建立一条实边
pushup(x); //更新节点x及其父节点的信息
}
}
void makeroot(int x){ //将节点x旋转到原树的根节点位置
access(x); //在原树上建立到节点x的实链
splay(x); //节点x成为Splay树根
reverse(x); //翻转节点x的子树
}
void split(int x,int y){ //把原树上以x为起点、y为终点的路径，生成一条实链
makeroot(x); //使节点x成为原树根
access(y); //在原树上建立到节点y的实链
splay(y); //使节点y成为Splay树，根在最右边就没有右儿子，所以右儿子为空
//只为了操作0就没必要执行Splay，但是在cut()函数里有用，所以执行Splay
}
void link(int x,int y){ //在结点x和y之间连接一条边
makeroot(x); //将节点x旋转到原树的根节点位置
t[x].fa=y; //节点x的父节点设置为节点y
}
void cut(int x,int y){ //将x,y的边切断
split(x,y); //点x至节点y的路径构成一条实链
if(t[y].ch[0]!=x||rc) return; //检查节点y的左子节点是否为节点x，且节点x无右子节点，说明x与y存在边
t[x].fa=t[y].ch[0]=0; //将节点y的左子节点设为空，
pushup(x); //更新节点x的sum值
}
int findroot(int x){ //查找x在原树上的根
access(x); //x与原树的树根的路径构成一条实链
splay(x); //同条实链在辅助树上，位于同一棵Splay树，将节点x成为Splay树根，原树根最浅所以肯定在最左端的位置
while(lc) pushdown(x),x=lc; //找Splay树最左端的结点
return x;
}
int main(){
int n,m; scanf("%d%d",&n,&m); //节点数量、操作次数
for(int i=1;i<=n;++i){ scanf("%d",&t[i].val); t[i].sum = t[i].val; } //记录节点
while(m--){
int opt,a,b; scanf("%d%d%d",&opt,&a,&b);
switch(opt){
case 0: split(a,b); printf("%d\n",t[b].sum); break;
case 1: if(findroot(a) != findroot(b))link(a,b); break;
case 2: cut(a,b); break;
case 3: splay(a); t[a].val=b; break;
}
}
return 0;
}
笔记：LCA是针对动态变化的树所生成的算法，可以进行，连接，断开，修改和查询。LCA是先把树分成多条链，查询的时候将查询的路径转化为重链，重链是父子节点都认识，“轻链”是子节点认父，父不认子，子节点称为“认父指针”。原树转化成辅助树，代码只需要储存和处理辅助树，为了保证实链是一条路径，实链上的节点只能有一个孩子，轻链足够还原出原树路径。access(x)函数是所有操作的基本步骤，作用是建立一条从根到x的实链。因为“认父指针”所以在很多操作的时候，需要将x旋到根节点。