LCT求调

#include<iostream>
#define ls son[x][0]
#define rs son[x][1]
#define ll  long long
using namespace std;
const ll N=2e5+5;
struct lct{
    ll son[N][2],fa[N],sum[N],ssum[N],v[N],tag[N];
    ll s[N],t,osum[N],ossum[N];
    void pushup(ll x){
        sum[x]=osum[x]+sum[ls]+sum[rs]+v[x];
        ssum[x]=ossum[x]+ssum[ls]+ssum[rs]+sum[x]*sum[x];
    }
    void push(ll x){
        swap(ls,rs);
        tag[x]^=1;
    }
    void pushdown(ll x){
        if(tag[x]){
            push(ls);
            push(rs);
            tag[x]=0;
        }
    }
    bool isroot(ll x){
        return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
    }
    void rotate(ll x){
        ll y=fa[x],z=fa[y];
        ll k=son[y][1]==x,w=son[x][k^1];
        if(!isroot(y)) son[z][son[z][1]==y]=x;
        son[x][k^1]=y;son[y][k]=w;
        fa[x]=z;fa[y]=x;
        if(w) fa[w]=y;
        pushup(y);
    }
    void splay(ll x){
        s[t=1]=x;
        for(ll i=x;!isroot(i);i=fa[i]) s[++t]=fa[i];
        for(ll i=t;i;i--) pushdown(s[i]);
        while(!isroot(x)){
            ll y=fa[x],z=fa[y];
            if(!isroot(y)) (son[z][0]==y)^(son[y][0]==x)?rotate(x):rotate(y);
            rotate(x);
        }
        pushup(x);
    }
    void access(ll x){
        for(ll y=0;x;x=fa[y=x]){
            splay(x);
            osum[x]+=sum[son[x][1]];
            ossum[x]+=ssum[son[x][1]];
            son[x][1]=y;
            osum[x]-=sum[y];
            ossum[x]-=ssum[y];
            pushup(x);
        }
    }
    void makeroot(ll x){
        access(x);
        splay(x);
        push(x);
    }
    ll find(ll x){
        access(x);
        splay(x);
        while(ls){
            pushdown(x);
            x=ls;
        }
        splay(x);
        return x;
    }
    void change(ll x,ll val){
        makeroot(x);
        v[x]=val;
        pushup(x);
    }
    void link(ll x,ll y){
        makeroot(x);
        if(find(y)!=x) fa[x]=y;
    }
}T;
ll n,m;
ll a[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<n;i++){
        ll u,v;
        cin>>u>>v;
        T.link(u,v);
    }
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        T.change(i,a[i]);
    }
    for(ll i=1;i<=m;i++){
        ll opt,x,y;
        cin>>opt>>x;
        if(opt==1){
            cin>>y;
            T.change(x,y);
        }else{
            T.makeroot(x);
            cout<<T.ssum[x]<<"\n";
        }
    }
    cout<<flush;
    return 0;
}