【BZOJ 4034】[HAOI2015]树上操作 差分+dfs序+树状数组

我们只要看出来这道题 数组表示的含义就是 某个点到根节点路径权值和就行 那么我们可以把最终答案 看做 k*x+b x就是其深度 ，我们发现dfs序之后，修改一个点是差分一个区间，修改一个点的子树，可以看做对于子树中的每一个点进行 a*(deep[x]-deep[root]+1) root是子树根节点，那么我们对 k 用a差分区间 对b用 -a*(deep[root]-1)差分区间

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#define MAXN 100010

using namespace std;

typedef long long LL;

LL k[MAXN],b[MAXN];

int n,m;

inline LL sum_k(int x)

{

    LL sum=;

    while(x>) sum+=k[x],x-=x&(-x);

    return sum;

}

inline void ins_k(int x,LL key)

{

    while(x<=n) k[x]+=key,x+=x&(-x);

}

inline LL sum_b(int x)

{

    LL sum=;

    while(x>) sum+=b[x],x-=x&(-x);

    return sum;

}

inline void ins_b(int x,LL key)

{

    while(x<=n) b[x]+=key,x+=x&(-x);

}

int l[MAXN],r[MAXN];

struct VIA

{

    int to,next;

}c[MAXN<<];

int head[MAXN],t,Ti,deep[MAXN];

inline void add(int x,int y)

{

  c[++t].to=y;

  c[t].next=head[x];

  head[x]=t;

}

void dfs(int x)

{

   l[x]=++Ti;

   for(int i=head[x];i;i=c[i].next)

   if(l[c[i].to]==)

   {

     deep[c[i].to]=deep[x]+;

     dfs(c[i].to);

   }

   r[x]=Ti;

}

int temp[MAXN];

inline void Init()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&temp[i]);

    for(int i=;i<n;i++)

    {

       int x,y;

       scanf("%d%d",&x,&y);

       add(x,y);

       add(y,x);

    }

    deep[]=;

    dfs();

    for(int i=;i<=n;i++)

     ins_b(l[i],temp[i]),ins_b(r[i]+,-temp[i]);

}

inline void work()

{

    while(m--)

    {

      int opt,x,a;

      scanf("%d%d",&opt,&x);

      if(opt==)

      {

        scanf("%d",&a);

        ins_b(l[x],a),ins_b(r[x]+,-a);

      }else

      if(opt==)

      {

        scanf("%d",&a);

        ins_k(l[x],a),ins_k(r[x]+,-a);

        ins_b(l[x],-(LL)a*(deep[x]-)),ins_b(r[x]+,(LL)a*(deep[x]-));

      }else

      {

        LL ans=sum_k(l[x])*deep[x]+sum_b(l[x]);

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

      }

    }

}

int main()

{

    Init();

    work();

    return ;

}