又wa了一下午。。。

思路

树的先序遍历顺序刚好对应线段树的一个区间，利用这一点直接dfs建序，然后再建线段树来查询修改就可以了。

1 #define dbg(x) cout<<#x<<" = "<< (x)<< endl  2 #define IO std::ios::sync_with_stdio(0);  3 #include 
     
        4 #define iter ::iterator  5 using namespace  std;  6 typedef long long ll;  7 typedef pair
      
       P;  8 #define pb push_back  9 #define se second 10 #define fi first 11 #define rs o<<1|1 12 #define ls o<<1 13 const ll inf=0x7fffffff; 14 const int N=5e4+10; 15 int l1[N],r1[N],fa[N]; 16 ll w[N],t[N]; 17 vector
       
        g[N]; 18 int n,q,cnt; 19 struct node{ 20     ll sumv,add; 21 }a[N*4]; 22 void dfs(int u){ 23     l1[u]=++cnt; 24     t[cnt]=u; 25     for(int i=0;i
        
         =ql&&r<=qr){ 57         a[o].sumv+=1ll*(r-l+1)*k; 58         a[o].add+=k; 59         return; 60     } 61     down(o,l,r); 62     int m=(l+r)/2; 63     if(ql<=m)up(ls,l,m,ql,qr,k); 64     if(qr>m)up(rs,m+1,r,ql,qr,k); 65     push(o); 66 } 67 ll qu(int o,int l,int r,int ql,int qr){ 68     if(l>=ql&&r<=qr){ 69         return a[o].sumv; 70     } 71     down(o,l,r); 72     int m=(l+r)/2; 73     ll res=0; 74     if(ql<=m)res+=qu(ls,l,m,ql,qr); 75     if(qr>m)res+=qu(rs,m+1,r,ql,qr); 76     return res; 77 } 78 int main(){ 79     scanf("%d%d",&n,&q); 80     for(int i=2;i<=n;i++){ 81         scanf("%d%lld",&fa[i],&w[i]); 82         fa[i]++; 83         g[fa[i]].pb(i); 84     } 85     dfs(1); 86     build(1,1,cnt); 87     while(q--){ 88         char s[10]; 89         scanf("%s",s); 90         ll x,y,z; 91         scanf("%d%lld%lld",&x,&y,&z); 92         x++; 93         if(s[0]=='A'){ 94             ll res=qu(1,1,cnt,l1[x],r1[x]); 95             ll h=r1[x]-l1[x]+1; 96             if(res<1ll*y*h){ 97                 up(1,1,cnt,l1[x],r1[x],z); 98             } 99         }100         else{101             ll res=qu(1,1,cnt,l1[x],l1[x]);102             if(res