【题目描述】

【思路】

树链剖分，两次dfs将重链转换成连续区间，然后用线段树维护区间和

#include
    
     #define node tree[id]#define lson tree[id<<1]#define rson tree[id<<1|1]using namespace std;typedef long long ll;const int maxn=50005;struct Tree{    int left,right;    ll lazy,sum;};int n,m,cnt;int w[maxn];vector
     
       g[maxn];int f[maxn],d[maxn],num[maxn],son[maxn];int id[maxn],eid[maxn],rk[maxn],top[maxn];Tree tree[maxn<<2];void dfs(int u,int fa,int dep){    d[u]=dep;    num[u]=1;    for(int i=0;i
      
       >1;    build(id<<1,le,mid);    build(id<<1|1,mid+1,ri);    pushup(id);}ll query(int id,int le,int ri){    if(node.left==le && node.right==ri){        return node.sum;    }    pushdown(id);    int mid=(node.left+node.right)>>1;    if(ri<=mid) return query(id<<1,le,ri);    else if(le>mid) return query(id<<1|1,le,ri);    else return query(id<<1,le,mid)+query(id<<1|1,mid+1,ri);}void update(int id,int le,int ri,ll val){    if(node.left==le && node.right==ri){        node.sum+=val*(node.right-node.left+1);        node.lazy+=val;        return;    }    pushdown(id);    int mid=(node.left+node.right)>>1;    if(ri<=mid) update(id<<1,le,ri,val);    else if(le>mid) update(id<<1|1,le,ri,val);    else{        update(id<<1,le,mid,val);        update(id<<1|1,mid+1,ri,val);    }    pushup(id);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n-1;++i){        scanf("%d%d",&f[i],&w[i]);		son[i]=-1;		int u=i,v=f[i];        g[u].push_back(v);        g[v].push_back(u);    }    f[0]=son[0]=-1;    dfs(0,-1,0);    dfs2(0,0);    build(1,1,n);    while(m--){        char op[2];        int x,y,z;        scanf("%s%d%d%d",op,&x,&y,&z);        if(op[0]=='S'){            ll now=query(1,id[x],id[x]);            if(now