#include<bits/stdc++.h>
using namespace std;
const int maxn=150002;
int n,m,s[maxn],fa[maxn],c[2][maxn],rev[maxn],f[maxn],F[maxn],v[maxn],V[maxn];
inline void read(int &x){
char ch=getchar();x=0;int f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}
inline int findfa(int x){return x==f[x]?x:f[x]=findfa(f[x]);}
inline int Findfa(int x){return x==F[x]?x:F[x]=Findfa(F[x]);}
inline bool isroot(int x){return c[0][findfa(fa[x])]!=x && c[1][findfa(fa[x])]!=x;}
void pushup(int x){s[x]=s[c[0][x]]+s[c[1][x]]+v[x];}
void pushdown(int x){
if(rev[x]){
swap(c[0][x],c[1][x]);
if(c[0][x])rev[c[0][x]]^=1;
if(c[1][x])rev[c[1][x]]^=1;
rev[x]=0;
}
}
void rotate(int x){
int y=findfa(fa[x]),z=findfa(fa[y]),whic=(x==c[1][y]);
if(!isroot(y))c[y==c[1][z]][z]=x;
fa[x]=z,fa[y]=x,c[whic][y]=c[whic^1][x];
if(c[whic^1][x])fa[c[whic^1][x]]=y;c[whic^1][x]=y;
pushup(y),pushup(x);
}
int tmp[maxn],top;
void splay(int x){
tmp[top=1]=x;
for(int i=x;!isroot(i);)tmp[++top]=i=findfa(fa[i]);
for(;top;top--)pushdown(tmp[top]);
while(!isroot(x)){
int y=findfa(fa[x]),z=findfa(fa[y]);
if(!isroot(y))rotate((c[1][y]==x)^(c[1][z]==y)?x:y);
rotate(x);
}
}
void access(int x){for(int y=0;x;x=findfa(fa[y=x]))splay(x),c[1][x]=y,pushup(x);}
void makeroot(int x){access(x),splay(x),rev[x]^=1;}
void dfs(int x,int fat){
f[x]=fat;
pushdown(x);
if(c[0][x])dfs(c[0][x],fat);
if(c[1][x])dfs(c[1][x],fat);
}
int main(){
read(n);read(m);
for(int i=1;i<=n;i++)read(v[i]),V[i]=s[i]=v[i],f[i]=F[i]=i;
int opt,a,b;
for(;m;m--){
read(opt),read(a),read(b);
if(opt==1){
a=findfa(a),b=findfa(b);
if(a==b)continue;
makeroot(a),access(b),splay(b);
if(Findfa(a)!=Findfa(b))fa[a]=b,F[F[a]]=F[b];else v[b]=s[b],dfs(b,b),c[0][b]=c[1][b]=0;
}
if(opt==2){int d=a;a=findfa(a);splay(a),v[a]+=b-V[d],V[d]=b,pushup(a);}
if(opt==3){
a=findfa(a),b=findfa(b);
if(Findfa(a)!=Findfa(b))printf("-1\n");
else makeroot(a),access(b),splay(b),printf("%d\n",s[b]);
}
}
return 0;
}
转载于:https://www.cnblogs.com/MikuKnight/p/9399610.html
相关资源：JAVA上百实例源码以及开源项目
