题目描述

有一棵点数为 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 。

题解

　不得不说大佬的思路真是非常厉害

　　我们考虑一下，对一个节点的单点修改会对它整棵子树的答案都产生影响，相当于给它的整个子树都加上一个值，也就是子树的答案都变化了$z$

　　然后考虑给以某个节点为根的子树增加权值，那么节点$y$增加的权值就是$dep[y]*z-(dep[x]-1)*z$，那么我们可以看成是$x$的子树中的每一个节点的答案都变化了$-(dep[x]-1)*z$，那么查询的时候只要记录下每一个节点的$z$值总和$a$，以及上面的变化总和$b$，那么答案就是$a*dep[y]+b$

　　区间修改，单点查询，只要用dfs序+线段树即可

　　ps：然后我抄看代码的时候有一个细节没有弄懂，为啥他每次pushdown的时候可以把$a,b$传给儿子之后自己清零。后来想了想发现因为是单点查询，节点都在最底端，所以上面的点清零对他们没有影响，因为他们的答案已经加上了影响，而且最底端的点不可能再pushdown下去，所以代码没问题，而且能防止上面的点的贡献重复加给下面的点

1 //minamoto 2 #include
     
       3 #define ll long long 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 inline int read(){ 8     #define num ch-'0' 9     char ch;bool flag=0;int res;10     while(!isdigit(ch=getc()))11     (ch=='-')&&(flag=true);12     for(res=num;isdigit(ch=getc());res=res*10+num);13     (flag)&&(res=-res);14     #undef num15     return res;16 }17 char sr[1<<21],z[20];int C=-1,Z;18 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}19 inline void print(ll x){20     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;21     while(z[++Z]=x%10+48,x/=10);22     while(sr[++C]=z[Z],--Z);sr[++C]='\n';23 }24 const int N=100005;25 int ver[N<<1],Next[N<<1],head[N],sz[N],dfn[N],fa[N],tot,num;26 ll a[N<<2],b[N<<2],val[N],dis[N];27 int n,m;28 inline void add(int u,int v){29     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;30     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;31 }32 void dfs(int u){33     dis[u]=dis[fa[u]]+1,dfn[u]=++num,sz[u]=1;34     for(int i=head[u];i;i=Next[i]){35         int v=ver[i];36         if(v!=fa[u]){37             fa[v]=u,dfs(v),sz[u]+=sz[v];38         }39     }40 }41 inline void pushdown(int p){42     a[p<<1]+=a[p],a[p<<1|1]+=a[p];43     b[p<<1]+=b[p],b[p<<1|1]+=b[p];44     a[p]=b[p]=0;45 }46 void update(int p,int l,int r,int ql,int qr,ll x,ll y){47     if(ql<=l&&qr>=r) return (void)(a[p]+=x,b[p]+=y);48     pushdown(p);49     int mid=l+r>>1;50     if(ql<=mid) update(p<<1,l,mid,ql,qr,x,y);51     if(qr>mid) update(p<<1|1,mid+1,r,ql,qr,x,y);52 }53 ll query(int u,int x,int p,int l,int r){54     if(l==r) return dis[u]*a[p]+b[p];55     pushdown(p);56     int mid=l+r>>1;57     if(x<=mid) return query(u,x,p<<1,l,mid);58     else return query(u,x,p<<1|1,mid+1,r);59 }60 int main(){61     n=read(),m=read();62     for(int i=1;i<=n;++i) val[i]=read();63     for(int i=1;i