HAOI 2015 树上操作

板子题，mark一下

就是第一发wa了一半，看讨论区大佬指出add的时候，最好开ll，不然int和ll一加炸了呜

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2*int(1e5)+7;
ll cnt=0,ecnt=0;
ll n,m,R,id[N],wt[N],top[N],son[N],head[N],fa[N],siz[N],dep[N];
ll mod,a[N<<2],lazy[N<<2],w[N];

struct lys{
    int from,to,nex;
}e[N*2];

void addedge(int from,int to){
    ecnt++;e[ecnt].from=from;e[ecnt].to=to;e[ecnt].nex=head[from];head[from]=ecnt;
}

void dfs1(int u,int f){
    siz[u]=1;
    fa[u]=f;
    dep[u]=dep[f]+1;
    int maxson=-1;
    for(int i=head[u];i;i=e[i].nex){
        int to=e[i].to;
        if(to==f) continue;
        dfs1(to,u);
        siz[u]+=siz[to];
        if(siz[to]>maxson) son[u]=to,maxson=siz[to];
    }
}

void dfs2(int u,int topf){
    cnt++;// new id
    id[u]=cnt;
    wt[cnt]=w[u];
    top[u]=topf;
    if(!son[u]) return;
    dfs2(son[u],topf);
    for(int i=head[u];i;i=e[i].nex){
        int to=e[i].to;
        if(to==son[u]||to==fa[u]) continue;
        dfs2(to,to);
    }
}

void build(int rt,int l,int r){
    if(l==r){
        a[rt]=wt[r];return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    a[rt]=a[rt<<1]+a[rt<<1|1];
}

void pushdown(int rt,int l,int r){
   if(lazy[rt]){
        int mid=(l+r)>>1;
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        a[rt<<1]+=lazy[rt]*(mid-l+1);
        a[rt<<1|1]+=lazy[rt]*(r-mid);
     lazy[rt]=0;
   }    
}

void add(int rt,int l,int r,int ql,int qr,ll k){
//    cout<<rt<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    if(ql<=l&&r<=qr){
        a[rt]+=(r-l+1)*k;
        lazy[rt]+=k;
        return;
    }
    int mid=(l+r)>>1;
    if(lazy[rt]) pushdown(rt,l,r);
    if(ql<=mid) add(rt<<1,l,mid,ql,qr,k);
    if(mid<qr) add(rt<<1|1,mid+1,r,ql,qr,k); 
    a[rt]=a[rt<<1]+a[rt<<1|1];
}

void addpath(int x,int y,ll k){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        add(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    add(1,1,n,id[x],id[y],k);
}

ll query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return a[rt];
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    ll ans=0;
    if(mid>=ql) ans+=query(rt<<1,l,mid,ql,qr);
    if(mid<qr) ans+=query(rt<<1|1,mid+1,r,ql,qr); 
    // ? a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
    return ans; 
}

ll qpath(int x,int y){
    ll ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans+=query(1,1,n,id[x],id[y]);
    return ans;
}

void addson(int u,ll k){
    add(1,1,n,id[u],id[u]+siz[u]-1,k);
}

ll qson(int u){ 
    return query(1,1,n,id[u],id[u]+siz[u]-1);
}

int main(){
  freopen("lys.in","r",stdin);
std::ios::sync_with_stdio(false);
cin.tie(0); 
cout.tie(0);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;addedge(a,b);addedge(b,a);
    }

    dfs1(1,0);

    dfs2(1,1);

    build(1,1,n);

    for(int i=1;i<=m;i++){
        int op;cin>>op;

        if(op==1) {
          int x,a;cin>>x>>a;
          add(1,1,n,id[x],id[x],a);
        }
        else if(op==2){
          int x,a;cin>>x>>a;
          addson(x,a);
        }
        else {
            int x;cin>>x;
            cout<<qpath(x,1)<<endl;
        }
    }
}