题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式：

 

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to ， 表示该树中存在一条边 (from, to) 。再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

5 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3

输出样例#1： 

6913

说明

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。

 

树链剖分的裸题

每次暴力更改就好

注意这题需要开long long

 

 

#include
     
      #include
      
       #include
       
        #define ls k<<1#define rs k<<1|1#define LL long long using namespace std;const LL MAXN=1e6+10;inline char nc(){    static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p1=(p2=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:++*p1;}inline LL read(){    char c=getchar();LL x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}    return x*f;}LL root=1;struct node{    LL u,v,w,nxt;}edge[MAXN];LL head[MAXN];LL num=1;inline void AddEdge(LL x,LL y){    edge[num].u=x;    edge[num].v=y;    edge[num].nxt=head[x];    head[x]=num++;}struct Tree{    LL l,r,f,w,siz;}T[MAXN];LL a[MAXN],b[MAXN],tot[MAXN],idx[MAXN],deep[MAXN],son[MAXN],top[MAXN],fa[MAXN],cnt=0;void update(LL k){    T[k].w=T[ls].w+T[rs].w;}void PushDown(LL k){    if(!T[k].f) return ;    T[ls].w+=T[k].f*T[ls].siz;    T[rs].w+=T[k].f*T[rs].siz;    T[ls].f+=T[k].f;    T[rs].f+=T[k].f;    T[k].f=0;}LL dfs1(LL now,LL f,LL dep){    deep[now]=dep;        tot[now]=1;    fa[now]=f;    LL maxson=-1;    for(LL i=head[now];i!=-1;i=edge[i].nxt)    {        if(edge[i].v==f) continue;        tot[now]+=dfs1(edge[i].v,now,dep+1);        if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v;    }    return tot[now];}void dfs2(LL now,LL topf){    idx[now]=++cnt;    a[cnt]=b[now];    top[now]=topf;    if(!son[now]) return ;    dfs2(son[now],topf);    for(LL i=head[now];i!=-1;i=edge[i].nxt)        if(!idx[edge[i].v])            dfs2(edge[i].v,edge[i].v);}void Build(LL k,LL ll,LL rr){    T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1;    if(ll==rr)    {        T[k].w=a[ll];        return ;    }    LL mid=(ll+rr)>>1;    Build(ls,ll,mid);    Build(rs,mid+1,rr);    update(k);}void PointAdd(LL k,LL pos,LL val){    if(T[k].l==T[k].r)    {        T[k].w+=val;        return ;    }    PushDown(k);    LL mid=(T[k].l+T[k].r)>>1;    if(pos<=mid) PointAdd(ls,pos,val);    if(pos>mid)  PointAdd(rs,pos,val);    update(k);}void IntervalAdd(LL k,LL ll,LL rr,LL val){    if(ll<=T[k].l&&T[k].r<=rr)    {        T[k].w+=T[k].siz*val;        T[k].f+=val;        return ;    }    PushDown(k);    LL mid=(T[k].l+T[k].r)>>1;    if(ll<=mid) IntervalAdd(ls,ll,rr,val);    if(rr>mid)  IntervalAdd(rs,ll,rr,val);    update(k);}LL IntervalAsk(LL k,LL ll,LL rr){    LL ans=0;    if(ll<=T[k].l&&T[k].r<=rr)    {        ans+=T[k].w;        return ans;    }    PushDown(k);    LL mid=(T[k].l+T[k].r)>>1;    if(ll<=mid) ans+=IntervalAsk(ls,ll,rr);    if(rr>mid)  ans+=IntervalAsk(rs,ll,rr);    return ans;}LL TreeSum(LL x,LL y){    LL ans=0;    while(top[x]!=top[y])//不在同一条链内     {        if(deep[top[x]]
        
         deep[y]) swap(x,y);    ans+=IntervalAsk(1,idx[x],idx[y]);    return ans;}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    memset(head,-1,sizeof(head));    LL N=read(),M=read();    for(LL i=1;i<=N;i++) b[i]=read();    for(LL i=1;i<=N-1;i++)    {        LL x=read(),y=read();        AddEdge(x,y);AddEdge(y,x);    }    dfs1(root,0,1);    dfs2(root,root);    Build(1,1,N);    while(M--)    {        LL opt=read(),x,val;        if(opt==1)        {            x=read(),val=read();            PointAdd(1,idx[x],val);        }        else if(opt==2)        {            x=read(),val=read();            IntervalAdd(1,idx[x],idx[x]+tot[x]-1,val);        }        else        {            x=read();            printf("%lld\n",TreeSum(root,x));        }    }    return 0;}