51nod 1199 Money out of Thin Air（线段树+树剖分）

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 ll n, m, dfs_clock;

 int w[maxn],son[maxn],dfn[maxn],num[maxn];

 ll lazy[maxn<<];

 vector<int> G[maxn];

 struct node

 {

     int l, r;

     ll sum;

 }t[maxn<<];

 void dfs(int u)

 {

     dfn[u]=++dfs_clock;

     son[u]=;

     for(int i=;i<G[u].size();i++)

     {

         int v=G[u][i];

         dfs(v);

         son[u]+=son[v];

     }

 }

 void PushUp(int o)

 {

     t[o].sum=t[o<<].sum+t[o<<|].sum;

 }

 void PushDown(int o)

 {

     if(lazy[o])

     {

         lazy[o<<]+=lazy[o];

         lazy[o<<|]+=lazy[o];

         int m=t[o].r-t[o].l+;

         t[o<<].sum+=lazy[o]*(m-(m>>));

         t[o<<|].sum+=lazy[o]*(m>>);

         lazy[o]=;

     }

 }

 void build(int l ,int r, int o)

 {

     lazy[o]=;

     t[o].l=l;

     t[o].r=r;

     t[o].sum=;

     if(l==r)

     {

         t[o].sum=num[l];

         return;

     }

     int mid=(l+r)>>;

     build(l,mid,o<<);

     build(mid+,r,o<<|);

     PushUp(o);

 }

 void update(int ql, int qr, int l, int r, ll z, int o)

 {

     if(ql<=l && qr>=r)

     {

         t[o].sum+=(r-l+)*z;

         lazy[o]+=z;

         return;

     }

     PushDown(o);

     int mid=(l+r)>>;

     if(ql<=mid)  update(ql,qr,l,mid,z,o<<);

     if(qr>mid)  update(ql,qr,mid+,r,z,o<<|);

     PushUp(o);

 }

 ll query(int ql, int qr, int l, int r, int o)

 {

     if(ql<=l && qr>=r)  return t[o].sum;

     PushDown(o);

     int mid=(l+r)>>;

     ll ans=;

     if(ql<=mid)  ans+=query(ql,qr,l,mid,o<<);

     if(qr>mid)   ans+=query(ql,qr,mid+,r,o<<|);

     return ans;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     scanf("%d%d",&n,&m);

     for(int i=;i<n;i++)  G[i].clear();

     for(int i=;i<n;i++)

     {

         int p; scanf("%d%d",&p,&w[i]);

         G[p].push_back(i);

     }

     w[]=;

     dfs_clock=;

     dfs();

     for(int i=;i<n;i++)  num[dfn[i]]=w[i];

     build(,n,);

     char op[]; ll x, y, z;

     memset(lazy,,sizeof(lazy));

     while(m--)

     {

         scanf("%s%lld%lld%lld",op,&x,&y,&z);

         if(op[]=='S')

         {

             if(query(dfn[x],dfn[x],,n,)<y)  update(dfn[x],dfn[x],,n,z,);

         }

         else

         {

             if(query(dfn[x],dfn[x]+son[x]-,,n,)<son[x]*y)  update(dfn[x],dfn[x]+son[x]-,,n,z,);

         }

     }

     for(int i=;i<n;i++)  printf("%lld\n",query(dfn[i],dfn[i],,n,));

     return ;

 }