【树链剖分】树的统计

又是一道模板题难度的树链剖分，和软件包管理器 几乎一模一样就直接放代码， 题解

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+12;
int cnt,head[N],fa[N],son[N],deep[N],id[N],sum[N],ma[N];
int nu[N],top[N],idn,w[N],a[N];
int n,m,u,v,t;
string s;
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]; ma[x]=max(ma[x<<1],ma[x<<1|1]); }
void update(int x,int l,int r,int L,int R,int v)
{
  if( l==r ) { w[l]=v;sum[x]=v,ma[x]=v;return;}
  int mid=l+r>>1;
  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);
}
int getsum(int x,int l,int r,int L,int R)
{
  int ans=0;
  if( L<=l and r<=R ) return sum[x];
  int mid=l+r>>1;
  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;
}
int getmax(int x,int l,int r,int L,int R)
{
  int ans=-9999999;
  if( L<=l and r<=R ) return ma[x];
  int mid=l+r>>1;
  if( L<=mid ) ans=max(ans,getmax( x<<1,l,mid,L,R ) );
  if( R>mid ) ans=max(ans,getmax( x<<1|1,mid+1,r,L,R ) );
  return ans;
}
void dfs1(int x,int f,int dep)
{
  deep[x]=dep;
  fa[x]=f;
  nu[x]=1;
  int 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);
    nu[x]+=nu[y];
    if( nu[y]>maxson )
    {
      son[x]=y;
      maxson=nu[y];
    }
  }
}
void dfs2(int x,int topf)
{

  id[x]=++idn;
  w[idn]=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==son[x] || y==fa[x] ) continue;
    dfs2(y,y);
  }
}
int qsum(int u,int v)
{
  int ans=0;
  while( top[u]!=top[v] )
  {
    if( deep[ top[u] ]<deep[ top[v] ] ) swap(u,v);
    ans+=getsum( 1,1,n,id[ top[u] ],id[u]  );
    u=fa[top[u]];
  }
  if( deep[ u ]>deep[ v ] ) swap(u,v);
    ans+=getsum( 1,1,n,id[u],id[v] );
  return ans;
}
int qmax(int u,int v)
{
  int ans=-999999;
  while( top[u]!=top[v] )
  {
    if( deep[ top[u] ]<deep[ top[v] ] ) swap(u,v);
    ans=max(ans, getmax( 1 , 1 , n , id[ top[u] ] ,id[u]  ) );
    u=fa[top[u]];
  }
  if( deep[ u ]>deep[ v ] ) swap(u,v);
  ans=max( ans , getmax( 1,1,n,id[u],id[v] ) );
  return ans;
}
void build(int x,int l,int r)
{
  if(l==r) { sum[x]=w[l],ma[x]=w[l];return; }
  int mid=l+r>>1;
  build( x<<1,l,mid );
  build( x<<1|1,mid+1,r );
  pushup(x);
}
int main(){

  cin>>n;
  for(int i=1;i<=n-1;i++)
  {
    cin>>u>>v;
    addedge(u,v);
    addedge(v,u);
  }
  for(int i=1;i<=n;i++) cin>>a[i];
  dfs1(1,0,1);
  dfs2(1,1);
  build(1,1,n);
  cin>>m;
  while(m--)
  {
    cin>>s;
    cin>>u>>v;
    if( s=="QMAX" )
    {
      cout<<qmax(u,v)<<endl;
    }
    else if( s=="CHANGE" )
    {
      update(1,1,n,id[u],id[u],v);
    }
    else if( s=="QSUM" )
      cout<<qsum(u,v)<<endl;
  }

}