https://www.lydsy.com/JudgeOnline/problem.php?id=3091
https://blog.csdn.net/popoqqq/article/details/40823659
看题解吧，没什么好解释的。。。。板子题，
我觉得以后我写lct都可以像这样专门写个rev和add的函数出来，很好用。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
int n,m;
int fa[maxn]={},ch[maxn][]={};
long long siz[maxn]={},val[maxn]={},sum[maxn]={};
long long lsum[maxn]={},rsum[maxn]={};
long long num[maxn]={};long long ad[maxn]={};
int rev[maxn]={};int sta[maxn]={},tail=;
inline void updata(int x){
sum[x]=sum[ch[x][]]+sum[ch[x][]]+val[x];
siz[x]=siz[ch[x][]]+siz[ch[x][]]+; lsum[x]=lsum[ch[x][]]+lsum[ch[x][]]+(sum[ch[x][]]+val[x])*(siz[ch[x][]]+);
rsum[x]=rsum[ch[x][]]+rsum[ch[x][]]+(sum[ch[x][]]+val[x])*(siz[ch[x][]]+); num[x]=num[ch[x][]]+num[ch[x][]]
+lsum[ch[x][]]*(siz[ch[x][]]+)
+rsum[ch[x][]]*(siz[ch[x][]]+)
+val[x]*(siz[ch[x][]]+)*(siz[ch[x][]]+);
}
inline long long hex(long long x){return x*(x+)/;}
inline long long hex2(long long x){return x*(x+)*(x+)/;}
void Add(int x,long long v){
ad[x]+=v; sum[x]+=siz[x]*v; val[x]+=v;
lsum[x]+=hex(siz[x])*v;
rsum[x]+=hex(siz[x])*v;
num[x]+=hex2(siz[x])*v;
}
void Rev(int x){
swap(ch[x][],ch[x][]);
swap(lsum[x],rsum[x]);
rev[x]^=;
}
inline void downdata(int x){
if(rev[x]){
if(ch[x][])Rev(ch[x][]);
if(ch[x][])Rev(ch[x][]);
updata(x);
rev[x]=;
}
if(ad[x]){
if(ch[x][])Add(ch[x][],ad[x]);
if(ch[x][])Add(ch[x][],ad[x]);
updata(x);
ad[x]=;
}
}
inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=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[y]=x;fa[x]=fy;
ch[y][l]=ch[x][r];ch[x][r]=y;
updata(y);
}
void Splay(int x){
int y,fy,w=x;sta[++tail]=x;
while(!isroot(w)){ sta[++tail]=fa[w]; w=fa[w]; }
while(tail)downdata(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];
}
}
int findfa(int x){
Access(x);Splay(x);
while(ch[x][])x=ch[x][];
return x;
}
void Reverse(int x){
Access(x);Splay(x);
Rev(x);
}
void Cut(int x,int y){
Reverse(x);Access(y);Splay(y);
if(ch[y][]==x&&!ch[x][]){fa[x]=;ch[y][]=;updata(y);}
}
void Link(int x,int y){
Reverse(x);
fa[x]=y;
}
long long mgcd(long long x,long long y){
long long z;
while(y){
z=x%y;x=y;y=z;
}return x;
}
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){scanf("%lld",&val[i]);siz[i]=;sum[i]=lsum[i]=rsum[i]=num[i]=val[i];}
int x,y,op;long long v,aa,bb;
for(int i=;i<n;i++){
scanf("%d%d",&x,&y); if(findfa(x)!=findfa(y))Link(x,y);
}
for(int i=;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if(op==){
if(findfa(x)==findfa(y))Cut(x,y);
}
else if(op==){
if(findfa(x)!=findfa(y))Link(x,y);
}
else if(op==){
scanf("%lld",&v);
if(findfa(x)==findfa(y)){
Reverse(x);Access(y);Splay(y);
Add(y,v);
}
}
else{
if(findfa(x)!=findfa(y)){printf("-1\n");}
else{
Reverse(x);Access(y);Splay(y);
aa=num[y];bb=hex(siz[y]);
v=mgcd(aa,bb);
printf("%lld/%lld\n",aa/v,bb/v);
}
}
}
}