=v=

因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量为0。当城市 被加派了k名士兵时。城市i的所有子城市需要被加派k+1名士兵。这些子城市的所有子城市需要被加派k+2名士兵。以此类推。

当然，加派士兵的同时，国王也需要不断了解当前的情况。于是他随时可能询问以城市i为根的子树中的所有城市共被加派了多少士兵。

你现在是国王的军事大臣，你能回答出国王的每个询问么？

= =

对于50%的数据，1<=n<=1000,1<=p<=300

对于100%的数据，1<=n<=50000,1<=p<=100000,1<=x<=n,0<=k<=1000

=w=

给第i点增加k个士兵，实际上一共增加了k*size[i]+w[i]。

其中w[i]是一个定值，可以O(n)预处理出来。

---

给原树转成dfs序后，

考虑询问一个点，它的贡献来源：

1.它及其儿子加的所有士兵：显然可以使用单点修改，区间询问的数据结构来维护；

2.其祖先加了士兵：祖先加的士兵会增加深度差后再传给这个点，所以用区间修改，单点询问的数据结构来维护三个东西：

(1)有多少个祖先加了士兵(2)加的士兵总和(3)祖先的总深度

OTZ

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const char* fin="truetears.in";const char* fout="truetears.out";const ll inf=0x7fffffff;const ll maxn=50007,maxm=maxn*2,maxt=maxn*4;ll n,m,i,j,k;ll fi[maxn],ne[maxm],la[maxm],tot;ll a[maxn],ans;ll fa[maxn],de[maxn],w[maxn],dfn[maxn],low[maxn],si[maxn];char ch;ll c[maxn],d[maxn][3],mk[maxt][3],num;void change(ll v,ll v1){    for (;v<=n;v+=v&-v) c[v]+=v1;}ll getsum(ll v){    ll k=0;    for (;v;v-=v&-v) k+=c[v];    return k;}ll getsum(ll l,ll r){    return getsum(r)-getsum(l-1);}void markdown(ll l,ll r,ll t){    if (l==r){        d[l][0]+=mk[t][0];        d[l][1]+=mk[t][1];        d[l][2]+=mk[t][2];    }else{        mk[t*2][0]+=mk[t][0];        mk[t*2][1]+=mk[t][1];        mk[t*2][2]+=mk[t][2];        mk[t*2+1][0]+=mk[t][0];        mk[t*2+1][1]+=mk[t][1];        mk[t*2+1][2]+=mk[t][2];    }    mk[t][0]=mk[t][1]=mk[t][2]=0;}void modify(ll l,ll r,ll t,ll v,ll u,ll v1,ll v2){    ll mid=(l+r)/2;    markdown(l,r,t);    if (l>v2 || r
          
           =v1 && r<=v2){ mk[t][0]+=v; mk[t][1]++; mk[t][2]+=u; return; } modify(l,mid,t*2,v,u,v1,v2); modify(mid+1,r,t*2+1,v,u,v1,v2);}void update(ll l,ll r,ll t,ll v){ ll mid=(l+r)/2; markdown(l,r,t); if (l==r) return; if (v<=mid) update(l,mid,t*2,v); else update(mid+1,r,t*2+1,v);}void add_line(ll a,ll b){ tot++; ne[tot]=fi[a]; la[tot]=b; fi[a]=tot;}void getw(ll v,ll from){ ll i,j,k; de[v]=de[from]+1; si[v]=1; dfn[v]=++num; for (k=fi[v];k;k=ne[k]) if (la[k]!=from){ getw(la[k],v); w[v]+=w[la[k]]+si[la[k]]; si[v]+=si[la[k]]; } low[v]=num;}int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d%d",&n,&m); for (i=2;i<=n;i++){ scanf("%d",&j); fa[i]=j; add_line(j,i); add_line(i,j); } getw(1,0); scanf("\n"); for (i=1;i<=m;i++){ scanf("%c%d",&ch,&j); if (ch=='A'){ scanf("%d\n",&k); change(dfn[j],si[j]*k+w[j]); if (dfn[j]==low[j]) continue; modify(1,n,1,k,de[j],dfn[j]+1,low[j]); }else{ scanf("\n"); ans=getsum(dfn[j],low[j]); update(1,n,1,dfn[j]); ans+=(d[dfn[j]][0]+d[dfn[j]][1]*de[j]-d[dfn[j]][2])*si[j]+w[j]*d[dfn[j]][1]; printf("%lld\n",ans); } } return 0;}
          
         
        
       
      
     

=o=

考虑贡献的来源。