题解 P6329

点分树模板题。是个神奇的算法。

点分树就是将分治重心按照层级连边，每个节点父亲的联通块都包含了当前节点的联通块，且高度为 \(\log n\)。可以解决不考虑树的形态的多次询问带修改的问题。

对于这道题，我们可以在点分树的每个节点上记录两棵树状数组，分别与当前节点距离为 \(k\) 的节点的权值和，以及与当前节点父亲距离为 \(k\) 的权值和。

这里的 LBT 要用 vector 存，空间复杂度 \(O(n\log n)\)。

查询的时候直接从点分树上对应的节点往上跳，一直到根。

加入当前节点 \(u\) 与 \(x\) 的距离为 \(dis\)，那么 \(u\) 的贡献为 \(sum_1[u][k-dis]-sum_2[u][k-dis]\)。需要减掉算重复的。

修改直接对根到 \(x\) 的链上的每个点改即可。

因为查询时 \(C_1,C_2\) 对应的范围相等，所以空间可以都开成联通块的大小。

复杂度 \(O(n\log^2n)\)。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=INT_MAX>>1;
int n,m,val[N],vis[N],f[N],tot,siz[N],sz[N],rt,fa[N][22],pre[N],dep[N];
vector<int>adj[N],c[2][N];
void getg(int u,int lst){
  siz[u]=1;f[u]=0;
  for(int i=0;i<adj[u].size();++i){
    int v=adj[u][i];if(v==lst||vis[v])continue;
    getg(v,u);siz[u]+=siz[v];f[u]=max(f[u],siz[v]);
  }
  f[u]=max(f[u],tot-siz[u]);
  if(f[u]<f[rt])rt=u;
}
int build(int u,int s){
  rt=0;tot=s;getg(u,0);
  int g=rt;
  vis[g]=1;sz[g]=s;
  for(int i=0;i<adj[g].size();++i){
    int v=adj[g][i],tmp;if(vis[v])continue;
    tmp=build(v,s-f[v]);pre[tmp]=g;
  }
  return g;
}
void dfs(int u,int lst){
  fa[u][0]=lst;dep[u]=dep[lst]+1;
  for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
  for(int i=0;i<adj[u].size();++i){
    int v=adj[u][i];if(v==lst)continue;
    dfs(v,u);
  }
}
int lca(int u,int v){
  if(dep[u]<dep[v])swap(u,v);
  for(int i=20;i>=0;--i)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
  if(u==v)return u;
  for(int i=20;i>=0;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
  return fa[u][0];
}
int lbt(int x){return x&(-x);}
void update(int id,int u,int i,int k){++i;for(;i<c[id][u].size();i+=lbt(i))c[id][u][i]+=k;}
int getsum(int id,int u,int i){int res=0;++i;int tmp=c[id][u].size()-1;i=min(i,tmp);for(;i;i-=lbt(i))res+=c[id][u][i];return res;}
int getdis(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
void modify(int u,int w){
  for(int i=u;i;i=pre[i])update(0,i,getdis(i,u),w);
  for(int i=u;pre[i];i=pre[i])update(1,i,getdis(pre[i],u),w);
}
int main(){
  //freopen("test.out","w",stdout);
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;++i)cin>>val[i];
  for(int i=1;i<n;++i){
    int u,v;cin>>u>>v;
    adj[u].push_back(v);adj[v].push_back(u);
  }
  f[0]=inf;
  build(1,n);dfs(1,0);
  for(int i=1;i<=n;++i)c[0][i].resize(sz[i]+2),c[1][i].resize(sz[i]+2);
  for(int i=1;i<=n;++i)modify(i,val[i]);
  int lst=0;
  while(m--){
    int op,x,y;cin>>op>>x>>y;x^=lst;y^=lst;
    if(op)modify(x,y-val[x]),val[x]=y;
    else{
      lst=getsum(0,x,y);
      for(int i=x;pre[i];i=pre[i]){
        int dis=getdis(pre[i],x);
        if(y>=dis){
          lst+=getsum(0,pre[i],y-dis)-getsum(1,i,y-dis);
        }
      }
      cout<<lst<<endl;
    }
  }
  return 0;
}