http://www.elijahqi.win/2018/01/28/bzoj1180-croatian2009otoci/
Description
給出n個結點以及每個點初始時對應的權值wi。起始時點與點之間沒有連邊。有3類操作： 1、bridge A B：詢問結點A與結點B是否連通。如果是則輸出“no”。否則輸出“yes”，并且在結點A和結點B之間連一條無向邊。 2、penguins A X：将結點A對應的權值wA修改為X。 3、excursion A B：如果結點A和結點B不連通，則輸出“impossible”。否則輸出結點A到結點B的路徑上的點對應的權值的和。給出q個操作，要求線上處理所有操作。資料範圍：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。
Input
#include<cstdio>
#include<algorithm>
#define N 33000
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int c[N][2],fa[N],v[N],n,m,top,q[N],sum[N];
bool rev[N];char op[10];
inline bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
inline void update(int x){sum[x]=sum[c[x][0]]+sum[c[x][1]]+v[x];}
inline void pushdown(int x){
int l=c[x][0],r=c[x][1];if (!rev[x]) return;
rev[l]^=1;rev[r]^=1;rev[x]=0;swap(c[x][0],c[x][1]);
}
inline void rotate(int x){
int y=fa[x],z=fa[y];
if (!isroot(y)) c[z][c[z][1]==y]=x;
int l=c[y][1]==x,r=l^1;
fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
}
inline void splay(int x){
q[top=1]=x;
for (int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
while(top) pushdown(q[top--]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y);
}rotate(x);
}
}
inline void access(int x){
for (int t=0;x;t=x,x=fa[x])
splay(x),
c[x][1]=t,
update(x);}
inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}
inline void print(int x){
pushdown(x);
if (c[x][0]) print(c[x][0]);
printf("%d %d %d %d\n",v[x],x,c[x][0],c[x][1]);
if (c[x][1]) print(c[x][1]);
}
inline int find(int x){access(x);splay(x);while(c[x][0])x=c[x][0];return x;}
int main(){
freopen("bzoj1180.in","r",stdin);
n=read();for (int i=1;i<=n;++i) v[i]=read();m=read();
for (int i=1;i<=m;++i){
scanf("%s",op);int x=read(),y=read();
if(op[0]=='e'){
if (find(x)!=find(y)) puts("impossible");
else {
// print(y),puts("laji");
// for (int i=1;i<=n;++i) printf("%d,fa[i]);puts("無語");
makeroot(x);
access(y);splay(y);printf("%d\n",sum[y]);
}
}
if (op[0]=='b') if (find(x)!=find(y)) puts("yes"),makeroot(x),fa[x]=y;else puts("no");
if (op[0]=='p') {
//print(x);puts("zhazha");access(x);print(x);puts("标記");splay(x);print(x);puts("标記");rev[x]^=1;
makeroot(x);
access(x);
splay(x);v[x]=sum[x]=y;//puts("1");puts("3");print(x);print(x);puts("1");print(x);puts("2");
}/*for (int i=1;i<=n;++i) printf("%d,fa[i]);puts("無語");
for (int i=1;i<=n;++i) printf("%d %d\n",c[i][0],c[i][1]);
for (int i=1;i<=n;++i) printf("%d,rev[i]);puts("\\");*/
}
return 0;
}