历史上有一个著名的王国

【题目描述】

历史上有一个著名的王国。它的所有城市互相连通并且构成一棵树。城市1

为首都也就是这棵树的根。

因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量

为0。当城市i 被加派了k 名士兵时。城市i 的所有子城市需要被加派k+1 名士

兵。这些子城市的所有子城市需要被加派k+2 名士兵。以此类推。

当然，加派士兵的同时，国王也需要不断了解当前的情况。于是他随时可

能询问以城市i 为根的子树中的所有城市共被加派了多少士兵。

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

【输入】

第一行，包含两个整数N,P 代表城市数量以及国王的命令的数量。

接下来的P 行，每行代表国王的一个命令，命令分两种

A X K 在城市X 加入K 个士兵

Q X 询问以城市X 为根的子树中所有士兵数量的和

【输出】

对于每个Q，输出答案。

【输入样例】

7 10

1 1 2 2 5 5

Q 1

A 2 1

Q 1

Q 2

Q 5

A 5 0

Q 5

A 3 1

Q 1

Q 2

【输出样例】

【数据范围】

对于50%的数据， 1<=N<=1000 1<=P<=300

对于100%的数据， 1<=N<=50000 1<=P<=100000 1<=X<=N 0<=K<=1000

题解

对以u为根的子树进行增加操作，即对以u为根的树上的每一个节点v增加k+dep[v]-dep[u]

其中k-dep[u]是这个操作的性质，而dep[v]是节点的性质，所以考虑分成两部分求解，用线段树维护两个值：total[u]和sum[u],分别表示对u节点操作了多少次和所有k-dep[u]的和，则

Query(u)=total[u]*sumdep[u]+sum[u]*size[u]，其中sumdep[u]表示以u为根的子树的所有节点v的dep[v]的和，size[u]表示以u为根的子树的节点个数，可以用一遍dfs求出。

  1 #include<cstdio>
  2 #ifdef WIN32
  3 #define putlong(x) printf("%I64d
",x);
  4 #else
  5 #define putlong(x) printf("%lld
",x);
  6 #endif
  7 using namespace std;
  8 struct listnode
  9 {
 10     int dest;
 11     listnode *next;
 12 }adj[100001];
 13 int index=0,id[50001],pre[50001],post[50001],dep[50001];
 14 void dfs(int u)
 15 {
 16     index++;
 17     id[index]=u;
 18     pre[u]=index;
 19     for(listnode *i=adj[u].next;i;i=i->next)
 20     {    
 21         dep[i->dest]=dep[u]+1;
 22         dfs(i->dest);
 23     }
 24     post[u]=index;
 25 }
 26 long long totlazy[200001],sumlazy[200001],sumdep[200001],le,ri,ans[200001],aug,__ans;
 27 void init(int o,int l,int r)
 28 {
 29     if(l==r)
 30         sumdep[o]=dep[id[l]];
 31     else
 32     {
 33         int m=(l+r)>>1;
 34         init(o<<1,l,m);
 35         init(o<<1|1,m+1,r);
 36         sumdep[o]=sumdep[o<<1]+sumdep[o<<1|1];
 37     }
 38 }
 39 void query(int o,int l,int r)
 40 {
 41     if(le<=l&&ri>=r)
 42         __ans+=ans[o];
 43     else
 44     {
 45         int m=(l+r)>>1;
 46         totlazy[o<<1]+=totlazy[o];
 47         totlazy[o<<1|1]+=totlazy[o];
 48         sumlazy[o<<1]+=sumlazy[o];
 49         sumlazy[o<<1|1]+=sumlazy[o];
 50         ans[o<<1]+=totlazy[o]*sumdep[o<<1]+sumlazy[o]*(m-l+1);
 51         ans[o<<1|1]+=totlazy[o]*sumdep[o<<1|1]+sumlazy[o]*(r-m);
 52         totlazy[o]=0;
 53         sumlazy[o]=0;
 54         if(le<=m)query(o<<1,l,m);
 55         if(ri>m)query(o<<1|1,m+1,r);
 56     }
 57 }
 58 void update(int o,int l,int r)
 59 {
 60     if(le<=l&&ri>=r)
 61     {
 62         totlazy[o]++;
 63         ans[o]+=sumdep[o];
 64         sumlazy[o]+=aug;
 65         ans[o]+=aug*(r-l+1);
 66     }
 67     else
 68     {
 69         int m=(l+r)>>1;
 70         totlazy[o<<1]+=totlazy[o];
 71         totlazy[o<<1|1]+=totlazy[o];
 72         ans[o<<1]+=totlazy[o]*sumdep[o<<1];
 73         ans[o<<1|1]+=totlazy[o]*sumdep[o<<1|1];
 74         totlazy[o]=0;
 75         sumlazy[o<<1]+=sumlazy[o];
 76         sumlazy[o<<1|1]+=sumlazy[o];
 77         ans[o<<1]+=sumlazy[o]*(m-l+1);
 78         ans[o<<1|1]+=sumlazy[o]*(r-m);
 79         sumlazy[o]=0;
 80         if(le<=m)update(o<<1,l,m);
 81         if(ri>m)update(o<<1|1,m+1,r);
 82         ans[o]=ans[o<<1]+ans[o<<1|1];
 83     }
 84 }
 85 int main()
 86 {
 87     freopen("c.in","r",stdin);
 88     freopen("c.out","w",stdout);
 89     int n(0),p(0);
 90     scanf("%d%d",&n,&p);
 91     listnode *a=adj+n+1;
 92     for(int i=2;i<=n;i++)
 93     {
 94         int x(0);
 95         scanf("%d",&x);
 96         a->dest=i;
 97         a->next=adj[x].next;
 98         adj[x].next=a++;
 99     }
100     dfs(1);
101     init(1,1,n);
102     char buf[10];
103     while(p--)
104     {
105         int x(0),k(0);
106         scanf("%s%d",buf,&x);
107         le=pre[x];
108         ri=post[x];
109         if(buf[0]=='A')
110         {
111             scanf("%d",&k);
112             aug=k-dep[x];
113             update(1,1,n);
114         }
115         else if(buf[0]=='Q')
116         {
117             __ans=0;
118             query(1,1,n);
119             putlong(__ans);
120         }
121     }
122     return 0;
123 }