P3833 [SHOI2012] 魔法树

有没有dalao知道为什么会TLE

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
int dfn[maxn],w[maxn],son[maxn],top[maxn],fa[maxn],siz[maxn],dep[maxn];
int sum[maxn<<2],lazy[maxn<<2];
vector<int> g[maxn];
int n,mm,cnt;

inline int read1(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0',ch=getchar();
    } 
    return x*f;
}

inline void write1(int x){
    if(x<0){
    	putchar('-'),x=-x;
	}
    if(x>9){
    	write1(x/10);
	}
    putchar(x%10+'0');
    return;
}

inline void dfs1(int u,int f){
    fa[u]=f;
    siz[u]=1;
    dep[u]=dep[f]+1;
    for(auto v:g[u]){
        if(v==f){
            continue;
        }
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<son[v]){
            son[u]=v;
        }
    }
}

inline void dfs2(int u,int tp){
    top[u]=tp;
    dfn[u]=++cnt;
    if(son[u]){
        dfs2(son[u],tp);
    }
    for(auto v:g[u]){
        if(v==fa[u]||v==son[u]){
            continue;
        }
        dfs2(v,v);
    }
}

inline void getup(int k){
    sum[k]=sum[k<<1]+sum[k<<1|1];
}

inline void pushdown(int k,int l,int r){
    if(lazy[k]){
        int m=(l+r)>>1;
        lazy[k<<1]+=lazy[k];
        lazy[k<<1|1]+=lazy[k];
        sum[k<<1]+=(m-l+1)*lazy[k];
        sum[k<<1|1]+=(r-m)*lazy[k];
        lazy[k]=0;
    }
}

inline void buildtree(int k,int l,int r){
    if(l==r){
        sum[k]=w[l];
        return ;
    }
    int m=(l+r)>>1;
    buildtree(k<<1,l,m);
    buildtree(k<<1|1,m+1,r);
    getup(k);
}

inline void add(int k,int l,int r,int x,int y,int val){
    if(x<=l&&y>=r){
        lazy[k]+=val;
        sum[k]+=(r-l+1)*val;
        return ;
    }
    pushdown(k,l,r);
    int m=(l+r)>>1;
    if(x<=m){
        add(k<<1,l,m,x,y,val);
    }
    if(y>=m+1){
        add(k<<1|1,m+1,r,x,y,val);
    }
    getup(k);
}

inline void add(int u,int v,int val){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]){
            swap(u,v);
        }
        add(1,1,n,dfn[top[u]],dfn[u],val);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]){
        swap(u,v);
    }
    add(1,1,n,dfn[v],dfn[u],val);
}

inline int query(int k,int l,int r,int x,int y){
    int res=0;
    if(x<=l&&y>=r){
        return sum[k];
    }
    pushdown(k,l,r);
    int m=(l+r)>>1;
    if(x<=m){
        res+=query(k<<1,l,m,x,y);
    }
    if(y>=m+1){
        res+=query(k<<1|1,m+1,r,x,y);
    }
    getup(k);
    return res;
}

signed main(){
    n=read1();
    memset(w,0,sizeof(w));
    for(int i=1;i<n;i++){
        int u,v;
        u=read1();
        v=read1();
        u++;
        v++;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    buildtree(1,1,n);
    mm=read1();
    for(int i=1;i<=mm;i++){
        char s;
        cin>>s;
        if(s=='A'){
            int x,y,val;
            x=read1();
            y=read1();
            val=read1();
            x++;
            y++;
            add(x,y,val);
        }
        else{
            int u;
            u=read1();
            u++;
            write1(query(1,1,n,dfn[u],dfn[u]+siz[u]-1));
            putchar('\n');
        }
    }
    return 0;
}