=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]是一个定值，可以
给原树转成dfs序后，
考虑询问一个点，它的贡献来源：
1.它及其儿子加的所有士兵：显然可以使用单点修改，区间询问的数据结构来维护；
2.其祖先加了士兵：祖先加的士兵会增加深度差后再传给这个点，所以用区间修改，单点询问的数据结构来维护三个东西：
(1)有多少个祖先加了士兵
(2)加的士兵总和
(3)祖先的总深度
OTZ
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define ll long long
using 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) return;
if (l>=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("
");
for (i=1;i<=m;i++){
scanf("%c%d",&ch,&j);
if (ch=='A'){
scanf("%d
",&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("
");
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
",ans);
}
}
return 0;
}=o=
考虑贡献的来源。