bzoj4034 树上操作

Description

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

Input

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

Output

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

 

Sample Input

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

Sample Output

6
9
13

HINT

用树状数组+DFS序

我们先用一个树状数组维护每一个点（的DFS序）到根节点的值，对于第一个操作，如果把x这个点+k，相当于把以x为根的子树的所有点都加上k，因为这棵子树的DFS序是连续的，所以可以用树状数组维护。而对于第二个操作，讲x的个点和其子树都+k，我们可以先假设，如果只往根节点+k，那么查询每一个点时，就相当于加上了其深度depth*k。如果要往其他点+k，我们可以令开一个树状数组，维护以x为根节点的子树的+k，然后，答案就是第一个树状数组+(depth当前点-depthx)*第二课树状数组。但是，我们在查询时并不知道depthx是什么，因此，在第二个操作时，让第一颗树状数组减去(depthx-1)*k。

#include 
#include 
#include 
#include 
#include 
#include 
#define REP(i,k,n)  for(long long i=k;i<=n;i++)
#define in(a) a=read()
#define MAXN 100010
using namespace std;
inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')
            f=-1;
    for(;isdigit(ch);ch=getchar())
        x=x*10+ch-'0';
    return x*f;
}
queue <long long> Q;
long long n,m;
long long total=0,head[MAXN],nxt[MAXN<<1],to[MAXN<<1];
long long l[MAXN],r[MAXN],depth[MAXN],dfn[MAXN],cnt;
long long tree[2][MAXN<<2];
long long arr[MAXN];
long long lowbit(long long k){
    return k & -k;
}
inline void adl(long long a,long long b){
    total++;
    to[total]=b;
    nxt[total]=head[a];
    head[a]=total;
    return ;
}
void dfs(long long u,long long fa){
    dfn[u]=l[u]=++cnt;
    for(long long e=head[u];e;e=nxt[e])
        if(to[e]!=fa){
            depth[to[e]]=depth[u]+1;
            dfs(to[e],u);
        }
    r[u]=cnt;
}
inline void add(long long f,long long s,long long k){
    for(long long i=s;i<=n;i+=lowbit(i))
        tree[f][i]+=k;
    return ;
}
inline long long query(long long f,long long s){
    long long sum=0;
    for(long long i=s;i;i-=lowbit(i))
        sum+=tree[f][i];
    return sum;
}
int main(){
    in(n),in(m);
    REP(i,1,n)
        in(arr[i]);
    long long a,b;
    REP(i,1,n-1)
        in(a),in(b),adl(a,b),adl(b,a);
    depth[1]=1;
    dfs(1,0);
    REP(i,1,n)
        add(1,l[i],arr[i]),add(1,r[i]+1,-arr[i]);
    long long pos,x;
    REP(i,1,m){
        in(pos),in(a);
        if(pos==1)  in(x),add(1,l[a],x),add(1,r[a]+1,-x);
        if(pos==2)  in(x),add(0,l[a],x),add(0,r[a]+1,-x),add(1,l[a],-x*(depth[a]-1)),add(1,r[a]+1,x*(depth[a]-1));
        if(pos==3)  printf("%lld\n",query(0,l[a])*depth[a]+query(1,l[a]));
    }
    return 0;
}
/*
5 5
1 2
1 4
2 3
2 5
*/