求解范围：（动态树问题）
- 树上路径查询、修改
- 动态连边、删边
- 换根
- lca
算法逻辑
概念：
- 类似树链剖分，把一棵树拆成许多链，每个链用splay维护（链上的为实边，否则为虚边），splay中以\(dep\)为关键字（左浅右深），splay里点之间用\(fa\)和\(son[0/1]\)连接，不同链之间用\(par\)连接（par是单向的（下->上））。
\(par\)存在splay的根中，值为该splay中 \(dep\) 最小（浅）的父亲（可以想象一下跳到原树中的那条链的顶端的父亲）
流程：
access
- 作用：将u往上到根的路径，拆成一条链
- 操作：
1.\(v\)为过程中一点，且到右儿子存在实边，则需要断开\(v\)与右端点的实边（变为虚边）。
2.\(u\)沿着par往上跳（直到根），每次到一个新的splay就跟上一个splay链合并一下。（同时更新1） - Code:
void access(int x) {
int y=0;
while(x) {
splay(x);P_dw(x);
if(son[x][1]) fa[son[x][1]]=0,par[son[x][1]]=x;
son[x][1]=y;fa[y]=x; //??splay
P_up(x);
y=x;x=par[x];
}
}
LCA(x,y)
- 操作：\(access(x)\),\(access(y)\)中\(y\)往上跳到与根在同一个splay里面时，所在的点\(d\)即为lca。
- 证明：
显然\(par\)的定义是到该splay树最浅的点的fa,然而\(d\)往下到\(y\)的第一条边为虚边，而且根据定义刚好跳到\(d\)。
小细节
- \(par\)是需要存储于每个splay_tree的根处，所以每次splay后要手动更新赋值。
- splay()前要手动递归从根到该点Pushdown。
- 可以不用\(par\)，只用\(fa\)，不过要慢一些呀。
ps.还有很多其余的操作可以见下面这道题的代码：
OTOCI
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
bool Lazy[N];
int val[N],son[N][2],sum[N];
int par[N],fa[N];
int q,n;
void P_up(int x) {sum[x]=val[x]+sum[son[x][0]]+sum[son[x][1]];}
void P_dw(int x) {
if(!Lazy[x])return;
swap(son[x][0],son[x][1]);
Lazy[son[x][0]]^=1,Lazy[son[x][1]]^=1;Lazy[x]=0;
}
bool Type(int x) {return son[fa[x]][1]==x;}
void rotate(int x) {
int y=fa[x],z=fa[y],k=Type(x);
fa[x]=z;if(z)son[z][Type(y)]=x;
son[y][k]=son[x][k^1];fa[son[y][k]]=y;
son[x][k^1]=y;fa[y]=x;
P_up(y);P_up(x);
}
void _spdw(int u,int x) {
if(!fa[u]) {par[x]=par[u];P_dw(u);return;}
_spdw(fa[u],x);
P_dw(u);
}
void splay(int x) {
_spdw(x,x);
for(int f=fa[x];f=fa[x];rotate(x)) {
if(fa[f]) rotate(Type(x)==Type(f)?f:x);
}
}
void access(int x) {
int y=0;
while(x) {
splay(x);P_dw(x);
if(son[x][1]) fa[son[x][1]]=0,par[son[x][1]]=x;
son[x][1]=y;fa[y]=x; //??splay
P_up(x);
y=x;x=par[x];
}
}
void mk_rt(int x) {access(x);splay(x);Lazy[son[x][0]]^=1;Lazy[son[x][1]]^=1;swap(son[x][0],son[x][1]);}
int Fd_rt(int x) {access(x);splay(x);while(son[x][0])x=son[x][0];splay(x);return x;}
void split(int x,int y) {mk_rt(x);access(y);splay(y);} //??
void Link(int x,int y) {mk_rt(x);par[x]=y;}
int Sum(int x,int y) {split(x,y);return sum[y];}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&val[i]),sum[i]=val[i];
scanf("%d",&q);
while(q--) {
char ch[21]; int x,y;
scanf("%s%d%d",ch,&x,&y);
if(ch[0]=='b') {
// printf("!%d %d\n",Fd_rt(x),Fd_rt(y));
if(Fd_rt(x)!=Fd_rt(y)) {printf("yes\n");Link(x,y);}
else printf("no\n");
}
else if(ch[0]=='p') {
splay(x);val[x]=y;P_up(x);
}
else {
// printf("!%d %d\n",Fd_rt(x),Fd_rt(y));
if(Fd_rt(x)!=Fd_rt(y)) {printf("impossible\n");continue;}
printf("%d\n",Sum(x,y));
}
}
return 0;
}