[HAOI2015]T2

【题目描述】

有一棵点数为N的树，以点1为根，且树点有边权。然后有M个操作，分为三种：

操作1：把某个节点x的点权增加a。

操作2：把某个节点x为根的子树中所有点的点权都增加a。

操作3：询问某个节点x到根的路径中所有点的点权和。

【输入格式】

第一行两个整数N,M，表示点数和操作数。

接下来一行N个整数，表示树中节点的初始权值。

接下来N-1行每行两个正整数fr,to，表示该树中存在一条边(fr,to)。

再接下来M行，每行分别表示一次操作。其中第一个数表示该操作的种类（1~3），之后接这个操作的参数（x或者x a）。

【输出格式】

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

【样例输入】

5 5

1 2 3 4 5

1 2

1 4

2 3

2 5

3 3

1 2 1

3 5

2 1 2

3 3

【样例输出】

【提示】

对于30%的数据，N,M<=1000

对于50%的数据，N,M<=100000且数据随机。

对于100%的数据，N,M<=100000，且所有输入数据的绝对值都不会超过10^6。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<vector>

 #include<queue>

 using namespace std;

 typedef long long LL;

 const LL maxn=;

 inline LL read(){

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 vector<LL> to[maxn];

 LL N,M;

 LL a[maxn];

 LL dep[maxn],fa[maxn],son[maxn],top[maxn],siz[maxn],id[maxn];

 LL val[maxn];

 LL num;

 inline void dfs1(LL rt,LL fath,LL deep){

     dep[rt]=deep; siz[rt]=; fa[rt]=fath;

     for(LL i=;i<to[rt].size();i++){

         LL y=to[rt][i];

         if(y!=fa[rt]){

             dfs1(y,rt,deep+);

             siz[rt]+=siz[y];

             if(siz[son[rt]]<siz[y]) son[rt]=y;

         }

     }

 }

 inline void dfs2(LL rt,LL tp){

     top[rt]=tp; id[rt]=++num;

     if(son[rt]!=) dfs2(son[rt],tp);

     for(LL i=;i<to[rt].size();i++){

         LL y=to[rt][i];

         if(y!=fa[rt]&&y!=son[rt]){

             dfs2(y,y);

         }

     }

 }

 struct node{

     LL l,r;

     LL sum,lazy;

 }tree[maxn*];

 inline void build(LL rt,LL l,LL r){

     tree[rt].l=l; tree[rt].r=r;

     if(l==r){

         tree[rt].sum=val[l];

         tree[rt].lazy=;

         return ;

     }

     LL mid=(l+r)>>;

     build(rt<<,l,mid); build(rt<<|,mid+,r);

     tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;

 }

 inline void update_son(LL rt){

     LL d=tree[rt].lazy;

     if(d!=){

         tree[rt<<].sum+=(tree[rt<<].r-tree[rt<<].l+)*d;

         tree[rt<<|].sum+=(tree[rt<<|].r-tree[rt<<|].l+)*d;

         tree[rt<<].lazy+=d; tree[rt<<|].lazy+=d;

         tree[rt].lazy=;

     }

 }

 inline void change(LL rt,LL l,LL r,LL delta){

     if(l<=tree[rt].l&&tree[rt].r<=r){

         tree[rt].sum+=(tree[rt].r-tree[rt].l+)*delta;

         tree[rt].lazy+=delta;

         return ;

     }

     update_son(rt);

     LL mid=(tree[rt].l+tree[rt].r)>>;

     if(l<=mid) change(rt<<,l,r,delta);

     if(mid+<=r) change(rt<<|,l,r,delta);

     tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;

 }

 inline LL query(LL rt,LL l,LL r){

     if(l<=tree[rt].l&&tree[rt].r<=r){

         return tree[rt].sum;

     }

     update_son(rt);

     LL ans=;

     LL mid=(tree[rt].l+tree[rt].r)>>;

     if(l<=mid) ans+=query(rt<<,l,r);

     if(mid+<=r) ans+=query(rt<<|,l,r);

      return ans;

 }

 inline void ASK(LL x){

     LL tp=top[x],ans=;

     while(x!=&&tp!=){

         ans+=query(,id[tp],id[x]);

         x=fa[tp]; tp=top[x];

     }

     printf("%lld\n",ans);

 }

 int main(){

     N=read(); M=read();

     for(LL i=;i<=N;i++) a[i]=read();

     for(LL i=,u,v;i<=N-;i++){

         u=read(); v=read();

         to[u].push_back(v); to[v].push_back(u);

     }

     dis[]=a[];

     dfs1(,,); dfs2(,);

     for(LL i=;i<=N;i++) val[id[i]]=a[i];

     build(,,num);

     for(LL i=,kin;i<=M;i++){

         kin=read();

         if(kin==){

             LL x=read(),d=read();

             change(,id[x],id[x],d);

         }

         else if(kin==){

             LL x=read(),d=read();

             change(,id[x],id[x]+siz[x]-,d);

         }

         else if(kin==){

             LL x=read();

             ASK(x);

         }

     }

     return ;

 }

巴特西