【树链剖分】树上操作

这道题和软件包管理器 几乎一模一样就直接放代码， 题解

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e6+12;
typedef long long ll;
ll son[N],fa[N],lazy[N],deep[N],top[N],siz[N],head[N],a[N],w[N],sum[N],id[N];
int cnt,nu,n,m,u,v,p;
struct {
  int to,nex;
}edge[N];
void addedge(int u,int v)
{
  edge[++cnt].to=v;
  edge[cnt].nex=head[u];
  head[u]=cnt;
}
void pushup(int x) { sum[x]=sum[x<<1]+sum[x<<1|1]; }
void pushdown(int x,int l,int r)
{
  if( !lazy[x] ) return;
  int mid=l+r>>1;
  sum[x<<1]+=(mid-l+1)*lazy[x];
  sum[x<<1|1]+=(r-mid)*lazy[x];
  lazy[x<<1]+=lazy[x];lazy[x<<1|1]+=lazy[x];
  lazy[x]=0;
}
void update(int x,int l,int r,int L,int R,ll v)
{
  if( L<=l and r<=R ) { sum[x]+=(r-l+1)*v;lazy[x]+=v;return; }
  int mid=l+r>>1;
  pushdown(x,l,r);
  if( L<=mid ) update( x<<1,l,mid,L,R,v );
  if( R>mid  ) update( x<<1|1,mid+1,r,L,R,v);
  pushup(x);
}
ll getsum(int x,int l,int r,int L,int R)
{
  if( L<=l and r<=R ) return sum[x];
  int mid=l+r>>1;
  pushdown(x,l,r);
  ll ans=0;
  if( L<=mid ) ans+=getsum(x<<1,l,mid,L,R);
  if( R>mid  ) ans+=getsum(x<<1|1,mid+1,r,L,R);
  return ans;
}
void dfs1(int x,int f,int dep)
{
  //cout<<x<<endl;
  fa[x]=f;
  deep[x]=dep;
  siz[x]=1;
  ll maxson=-1;
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( y==f ) continue;
    dfs1( y,x,dep+1 );
    siz[x]+=siz[y];
    if( siz[y]>maxson )
    {
      son[x]=y;
      maxson=siz[y];
    }
  }
}
void dfs2(int x,int topf)
{

  id[x]=++nu;
  w[nu]=a[x];
  top[x]=topf;
  if( !son[x] ) return;
  dfs2( son[x],topf );
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( y==fa[x] or y==son[x] ) continue;
    dfs2( y,y );
  }
}
void build( int x,int l,int r )
{
  if( l==r ) { sum[x]=w[l];return;}
  int mid=l+r>>1;
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  pushup(x);
}
ll qsum(int u)
{
  ll ans=0;
  while( top[u]!=1 )
  {
    ans+=getsum(1,1,n,id[top[u]],id[u]);
    u=fa[top[u]];
  }
  ans+=getsum(1,1,n,id[top[u]],id[u]);
  return ans;
}
 main(){
  //freopen("std.in","r",stdin);
  //freopen("std.out","w",stdout);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n-1;i++)
  {
    cin>>u>>v;
    addedge(u,v);
    addedge(v,u);
    //cout<<i<<endl;
  }
  dfs1(1,0,1);
  dfs2(1,1);
  build(1,1,n);
  //for(int i=1;i<=n;i++) cout<<top[i]<<" ";
  //cout<<endl;
  while(m--)
  {
    cin>>p;
    if( p==1 )
    {
      cin>>u>>v;
      update(1,1,n,id[u],id[u],v);
    }
    else if(p==2)
    {
      cin>>u>>v;
      update(1,1,n,id[u],id[u]+siz[u]-1,v);
    }
    else{
      cin>>u;
      cout<<qsum(u)<<endl;;
    }
  }
}