http://www.lydsy.com/JudgeOnline/problem.php?id=2843
https://blog.csdn.net/clove_unique/article/details/50992341
和之前那道题lct求两点距离用lca不同，这道题因为给的边的两个端点是没有顺序的（没法直接按照给的点直接将某个点连到树上），所以bridge需要区间翻转的操作，因为splay维护的是链，所以区间翻转相当于将叶子变成了根，根变成叶子(链翻转过来)，然后再把此时的根（x）连到y上就可以了。
penguins操作之后要access一下
excursion操作时，将x翻转为根再access y就能求出这一段上的企鹅数。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=;
int n,m; char f[]={};
int fa[maxn]={},ch[maxn][]={},siz[maxn]={};
int val[maxn]={},rev[maxn]={};
int sta[maxn]={},tail=;
int ds[maxn]={};
inline void updata(int x){ siz[x] = siz[ch[x][]] + siz[ch[x][]]+val[x];}
inline bool isroot(int x){ return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}
int getfa(int x){if(ds[x]==x)return x; return ds[x]=getfa(ds[x]);}
void rotate(int x){
int y=fa[x];int fy=fa[y];
int l=ch[y][]==x?:;int r=l^;
if(!isroot(y)){
if(ch[fy][]==y) ch[fy][]=x;
else ch[fy][]=x;
}
fa[ch[x][r]]=y;fa[x]=fy;fa[y]=x;
ch[y][l]=ch[x][r];ch[x][r]=y;
updata(y);
}
void Swapdata(int x){
if(rev[x]){
swap(ch[x][],ch[x][]);
if(ch[x][])rev[ch[x][]]^=;
if(ch[x][])rev[ch[x][]]^=;
rev[x]=;
}
}
void splay(int x){
int w=x;
int y,fy;sta[++tail]=x;
while(w&&!isroot(w)){sta[++tail]=fa[w];w=fa[w];}
while(tail){Swapdata(sta[tail--]);}
while(!isroot(x)){
y=fa[x];fy=fa[y];
if(!isroot(y)){
if((ch[fy][]==y)^(ch[y][]==x))rotate(x);
else rotate(y);
}rotate(x);
}updata(x);
}
void Access(int x){
int y=;
while(x){
splay(x);
ch[x][]=y;
updata(x);
y=x;x=fa[y];
}
}
void Reverse(int x){
Access(x);
splay(x);
rev[x]^=;
}
void Link(int x,int y){
Reverse(x);fa[x]=y;
splay(x);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&val[i]);
for(int i=;i<=n;i++)ds[i]=i;
scanf("%d",&m);
int x,y,xx,yy;
for(int i=;i<=m;i++){
scanf("%s",f);
scanf("%d%d",&x,&y);
if(f[]=='b'){
xx=getfa(x);yy=getfa(y);
if(xx==yy)printf("no\n");
else{
printf("yes\n");ds[xx]=yy;
if(x!=y)Link(x,y);
}
}
else if(f[]=='p'){
val[x]=y;Access(x);splay(x);
}
else{
xx=getfa(x);yy=getfa(y);
if(xx!=yy)printf("impossible\n");
else{
Reverse(x);Access(y);splay(y);
printf("%d\n",siz[y]);
}
}
}
return ;
}