LCT
给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。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和操作2，怎么做。没错！这就是个树剖。但是1和2要求我们动态维护树链，所以说很难受，没法用树剖做。
怎么办呢？我们可以用LCT！LCT是动态树的一种，支持在动态维护树的连接和断开的同时维护树链。具体来说，LCT中的每个树链是由splay来维护的，splay中的点的key是点的深度。由于确定了树根以后，树链上的点两两之间深度不同，所以不会出现两个点的key相同的情况。
原树中，链与链之间是有边的，但是一条链最多连出一条边，就是链顶结点连向上方的边。我们把链中的边称作实边，链与链之间的边称作虚边，那么虚边和实边显然共同组成了原树的所有边。
lct中，一个splay的key值相邻的两个点之间可以看作连有一条实边，同时splay的根又向上连了一条边，代表这条链连出的那条虚边。因此，lct中保存了原树的信息。我们在操作lct的时候要保证这些信息不丢失。
access是lct最基本的操作。它表示把x到root之间的路径打通变成一条链。
void access(int x){ //y:上一个splay的根 for (int y=0; x; y=x, x=fa[x]){ splay(x); son[x][1]=y; pushup(x); } } y代表前面处理过的那条链的splay根，x就是y这条链顶端所连的点。splay(x)之后，在x右边的点深度都大于x。把它们舍弃掉以后接上y，表示比x深度大的点是y这些点了。
由于给x接上了点，别忘记更新x的值。
接下来是makeroot操作，它把x变成原树的根。
void makert(int x){ access(x); splay(x); rev[x]^=1; } 思路很简单。先把x到根的路径打通。x要变成原树的根，就相当于这条链被翻转，所以把x变成splay的根后，在x上打一个rev标记，这样所有点的深度顺序都被反过来了，x也从深度最大的点变成了深度最小的点。
下面是find操作，它寻找原树的根。没什么好讲的，就是access以后在splay中不停往左走，找到深度最小的点。
接下来是get操作，get(x, y)表示拎出一条以x和y为端点的链，把x变成树根，并把y变成这条链splay的根。
void get(int x, int y){ makert(x); access(y); splay(y); } get没啥好说的。接下来终于到了我们需要的两个操作——link和cut。
link操作把x和y连在一起，相当于合并了两棵树。
void link(int x, int y){ makert(x); fa[x]=y; } 最后就是cut操作了，它把x和y的边断开。同时还顺便判断了一下x和y是不是有边：
void cut(int x, int y){ //仅当有边时才能断 get(x, y); if (fa[x]==y&&!son[x][1]) fa[x]=son[y][0]=0; pushup(y); } 显然，只有当x和y是key值相邻的点时才会有边。因此如果key值不相邻，那就可以直接不管它。别忘记y的值需要更新。
贴一下完整代码~
#include#include using namespace std;const int maxn=3e5+5;struct LCT{ int son[maxn][2], fa[maxn], rev[maxn], sum[maxn], w[maxn]; inline int which(int x){ return son[fa[x]][0]==x?0:1; } inline bool isrt(int x){ return son[fa[x]][0]!=x&&son[fa[x]][1]!=x; } inline void link(int f, int x, int p){ son[f][p]=x; fa[x]=f; } inline void pushup(int x){ sum[x]=sum[son[x][0]]^sum[son[x][1]]^w[x]; } inline void pushdown(int x){ rev[son[x][0]]^=rev[x]; rev[son[x][1]]^=rev[x]; if (rev[x]){ swap(son[x][0], son[x][1]); rev[x]=0; } } void spin(int x){ int f=fa[x], ff=fa[f]; bool frt=isrt(f); int wx=which(x), wf=which(f); link(f, son[x][!wx], wx); link(x, f, !wx); if (!frt) link(ff, x, wf); else fa[x]=ff; //必须这样写，因为它们有且只有它们两个的信息变动了 //然后就不用管sum的维护了 pushup(f); pushup(x); } void flagclear(int x){ if (!isrt(x)) flagclear(fa[x]); pushdown(x); } void splay(int x){ //splay后一条链上的标记都被清掉了 flagclear(x); for (; !isrt(x); spin(x)) if (!isrt(fa[x])) spin(which(x)==which(fa[x])?fa[x]:x); } void access(int x){ //y:上一个splay的根 for (int y=0; x; y=x, x=fa[x]){ splay(x); son[x][1]=y; pushup(x); } } void makert(int x){ access(x); splay(x); rev[x]^=1; } int find(int x){ access(x); splay(x); pushdown(x); while (son[x][0]) x=son[x][0], pushdown(x); return x; } //把x提根以后，打通y，用y当splay的根 void get(int x, int y){ makert(x); access(y); splay(y); } void link(int x, int y){ makert(x); fa[x]=y; } void cut(int x, int y){ //仅当有边时才能断 get(x, y); if (fa[x]==y&&!son[x][1]) fa[x]=son[y][0]=0; pushup(y); }}lct;int n, m;int main(){ scanf("%d%d", &n, &m); int op, x, y; for (int i=1; i<=n; ++i) scanf("%d", &lct.w[i]); for (int i=1; i<=m; ++i){ scanf("%d%d%d", &op, &x, &y); if (op==0) lct.get(x, y), printf("%d\n", lct.sum[y]); if (op==1) if (lct.find(x)!=lct.find(y)) lct.link(x, y); if (op==2) if (lct.find(x)==lct.find(y)) lct.cut(x, y); if (op==3) lct.w[x]=y, lct.splay(x); } return 0;}
显然，lct中的所有操作去除access都是\(O(logn)\)的。那么access操作的复杂度是多少呢？没错，它就是\(O(logn)\)！别问我为什么，钦定的。（逃）
