BZOJ 3091 城市旅行 (LCT)

/**************************************************************
    Problem: 3091
    User: SongHL
    Language: C++
    Result: Accepted
    Time:1764 ms
    Memory:6464 kb
****************************************************************/
 
//BZOJ 3091
//给出一棵无根树,维护四个操作:link,cut,路径加法,路径期望查询
#include<bits/stdc++.h>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
using namespace std;
const int maxn=50010;
int n,m,fa[maxn];
struct node{
    int son[2];
    LL sum,tag,rev,ans,val,lsum,rsum,size;
    int& operator [] (int x) {return son[x];}
}tree[maxn];
LL gcd(LL a,LL b) {return b==0 ? a : gcd(b,a%b);}
namespace LCT{
    void reverse(int k) 
    {
        swap(tree[k][0],tree[k][1]);
        swap(tree[k].lsum,tree[k].rsum);
        tree[k].rev^=1;
    }
     
    void add(int k,LL val) 
    {
        tree[k].val+=val;
        tree[k].sum+=tree[k].size*val;
        tree[k].tag+=val;
        tree[k].ans+=tree[k].size*(tree[k].size+1)*(tree[k].size+2)/6*val;
        tree[k].lsum+=tree[k].size*(tree[k].size+1)/2*val;
        tree[k].rsum+=tree[k].size*(tree[k].size+1)/2*val;
    }
    int find(int x) {return fa[x] ? find(fa[x]):x;}
     
    void pushdown(int k) 
    {
        if(tree[fa[k]][0]==k || tree[fa[k]][1]==k) pushdown(fa[k]);
        int l=tree[k][0],r=tree[k][1];
        if(tree[k].rev) 
        {
            if(l) reverse(l);
            if(r) reverse(r);
            tree[k].rev^=1;
        }
        if(tree[k].tag) 
        {
            if(l) add(l,tree[k].tag);
            if(r) add(r,tree[k].tag);
            tree[k].tag=0;
        }
    }
    void pushup(int k) 
    {
        int l=tree[k][0],r=tree[k][1];
        tree[k].size=tree[l].size+tree[r].size+1;
        tree[k].lsum=tree[l].lsum+(tree[l].size+1)*tree[k].val+tree[r].lsum+tree[r].sum*(tree[l].size+1);
        tree[k].rsum=tree[r].rsum+(tree[r].size+1)*tree[k].val+tree[l].rsum+tree[l].sum*(tree[r].size+1);
        tree[k].sum=tree[l].sum+tree[r].sum+tree[k].val;
        tree[k].ans=tree[l].ans+tree[r].ans+tree[l].lsum*(tree[r].size+1)+tree[r].rsum*(tree[l].size+1)+tree[k].val*(tree[l].size+1)*(tree[r].size+1);
    }
    void rotate(int x) 
    {
        int y=fa[x],z=fa[y],l,r;
        l=tree[y][1]==x;r=l^1;
        if(tree[z][0]==y || tree[z][1]==y) tree[z][tree[z][1]==y]=x;
        fa[tree[x][r]]=y;fa[x]=z;fa[y]=x;
        tree[y][l]=tree[x][r];tree[x][r]=y;
        pushup(y);pushup(x);
    }
    void splay(int x) 
    {
        pushdown(x);
        while(tree[fa[x]][0]==x || tree[fa[x]][1]==x) 
        {
            int y=fa[x],z=fa[y];
            if(tree[z][0]==y || tree[z][1]==y) 
            {
                if(tree[z][0]==y^tree[y][0]==x) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
    }
    void access(int x) //访问
    {
        for(int y=0;x;y=x,x=fa[x]) splay(x),tree[x][1]=y,pushup(x);
    }
    int findroot(int x)//找根(在真实的树中的)
    {
        access(x);splay(x);
        while(tree[x][0]) pushdown(x),x=tree[x][0];
        return x;
    }
    void makeroot(int x) //换根
    {
        access(x);splay(x);reverse(x);
    }
    void split(int x,int y)//提取路径
    {
        makeroot(x);
        access(y);splay(y);
    }
    void link(int x,int y) 
    {
        makeroot(x);fa[x]=y;
    }
    void cut(int x,int y) 
    {
        makeroot(x);access(y);splay(y);
        if(tree[y][0]==x && tree[x][1]==0)
            tree[y][0]=0,fa[x]=0,pushup(y);
    }
    void modify(int x,int y,LL val)//对x~y这段路径操作 
    {
        makeroot(x);access(y);
        splay(y);add(y,val);
    }
    void query(int x,int y) 
    {
        split(x,y);
        LL A=tree[y].ans,B=tree[y].size*(tree[y].size+1)/2;
        LL D=gcd(A,B);
        printf("%lld/%lld\n",A/D,B/D);
    }
}
using namespace LCT;
  
int main() 
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&tree[i].val);
    for(int u,v,i=1;i<n;i++) 
    {
        scanf("%d%d",&u,&v);
        link(u,v);
    }
    for(int op,x,y,d,i=1;i<=m;i++) 
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==1) if(find(x)==find(y)) cut(x,y);
        if(op==2) if(find(x)!=find(y)) link(x,y);
        if(op==3){ scanf("%d",&d); if(find(x)==find(y)) modify(x,y,d); }
        if(op==4) if(find(x)==find(y)) query(x,y); else puts("-1");
    }
    return 0;
}