这题其实就是树剖裸题啊。
然后毒瘤选手由于上题树剖被卡到哭所以选择dfs序+树状数组。
不得不说简单的算法做出来更加难思考。然后网上的dalao们都一笔带过净说什么用两个树状数组维护就可以啦。
经过大半小时的思考，代码实现还是非常简单。
这个值得详细讲讲。
假如我们弄一个树状数组，然后维护的是x到根的sum（其实就是询问的答案嘛），先看第一个操作，单点修改，那么改了这个点，相当于把他这一整棵子树的答案都加上了d，由于用dfs序重新编号，可以发现子树中的点都是连续的，那么树状数组改段求段就可以用差分数组解决。
问题在于第二个操作，修改了整个子树，对每个节点y的影响是d*(dep[x]-dep[y])，那么非常难受，因为每个点改变的值和dep有关，并不相同，怎么办？绝佳的方法就是我们忽略dep的影响，用另一个树状数组维护d，那么问题又来了，x肯定不是时时相同的，虽然询问y的时候可以知道dep[y]，但是dep[x]仍然不确定，为了可以确定，那么对于每次这种修改，我们就在第一个树状数组给它减去d*（dep[x]-1），这样一来，就把这个操作转化成增加x整个子树和x到根的路径上的点，那么对于每个点，增加的数就变成d*dep[y]，那么求解的时候，就可以心安理得的用第一个树状数组的值+第二个树状数组的值*d了。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; int n,m; struct node { int x,y,next; }a[210000];int len,last[110000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int z,dep[110000],l[110000],r[110000]; void dfs(int x,int f) { l[x]=++z; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=f) dep[y]=dep[x]+1, dfs(y,x); } r[x]=z; } //---------init----------------- LL s[2][110000]; int lowbit(int x){return x&-x;} void change(int w,int x,LL k) { while(x<=n) { s[w][x]+=k; x+=lowbit(x); } } LL getsum(int w,int x) { LL ret=0; while(x>=1) { ret+=s[w][x]; x-=lowbit(x); } return ret; } //-----------bit-------------- LL point[110000]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&point[i]); len=0;memset(last,0,sizeof(last)); int x,y; for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } z=0;dep[1]=1;dfs(1,0); //init for(int i=1;i<=n;i++) change(0,l[i],point[i]), change(0,r[i]+1,-point[i]); int op;LL d; for(int i=1;i<=m;i++) { scanf("%d",&op); if(op==1) { scanf("%d%lld",&x,&d); change(0,l[x],d); change(0,r[x]+1,-d); } else if(op==2) { scanf("%d%lld",&x,&d); change(0,l[x],-d*(dep[x]-1)); change(0,r[x]+1,d*(dep[x]-1)); change(1,l[x],d); change(1,r[x]+1,-d); } else { scanf("%d",&x); printf("%lld ", getsum(0,l[x]) + dep[x]*getsum(1,l[x]) ); } } return 0; }