思路

省选前回来复习个板子找找手感。

注意到点分治的结构形成树。

我们在逐层分治结构的各个核心分别维护一些树状数组，用来保存分支结构内距离为 $d$ 的点的权值之和；对每个子树都这么干。

修改时与其相关的分治重心是 $O(\log n)$ 的，直接逐个修改就好了。

查询答案时做一下容斥即可。

Code

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
struct BIT
{
    std::vector<uint>V;
    voi build(uint n){V.resize(n+1);}
    voi add(uint p,uint v){p++;while(p<V.size())V[p]+=v,p+=lowbit(p);}
    uint find(uint r)
    {
        uint ans=0;_min(r,(uint)V.size()-1u);
        while(r)ans+=V[r],r-=lowbit(r);
        return ans;
    }
};
bol Gone[100005];
std::vector<uint>Way[100005];
uint getsiz(uint p,uint f)
{
    uint ans=1;for(auto s:Way[p])if(!Gone[s]&&s!=f)ans+=getsiz(s,p);
    return ans;
}
uint getwp(uint p,uint f,uint siz,uint&wp,uint&wp_siz)
{
    uint w=1,t=0;
    for(auto s:Way[p])if(s!=f&&!Gone[s]){uint q=getwp(s,p,siz,wp,wp_siz);_max(t,q),w+=q;}
    _max(t,siz-w);if(_min(wp_siz,t))wp=p;
    return w;
}
BIT B[300005];uint tp=0;
struct Info{uint p,d;bol op;};
std::vector<Info>QwQ[100005];
uint IstInfo(uint p,uint f,uint dep,uint A,uint B)
{
    uint ans=dep;QwQ[p].push_back(Info{A,dep,true});QwQ[p].push_back(Info{B,dep,false});
    for(auto s:Way[p])if(s!=f&&!Gone[s])_max(ans,IstInfo(s,p,dep+1,A,B));
    return ans;
}
voi dfs(uint p)
{
    uint siz=getsiz(p,-1);{uint tmp=siz;getwp(p,-1,siz,p,tmp);}
    Gone[p]=true;uint id=tp++;B[id].build(siz+1);QwQ[p].push_back(Info{id,0,true});
    for(auto s:Way[p])if(!Gone[s]){uint d=IstInfo(s,-1,1,id,tp);B[tp++].build(d+1);}
    for(auto s:Way[p])if(!Gone[s])dfs(s);
}
voi add(uint p,uint v){for(auto I:QwQ[p])B[I.p].add(I.d,v);}
uint find(uint p,uint k)
{
    uint ans=0;
    for(auto s:QwQ[p])if(s.d<=k)s.op?ans+=B[s.p].find(k-s.d+1):ans-=B[s.p].find(k-s.d+1);
    return ans;
}
uint Val[100006];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
#endif
    uint n,m;scanf("%u%u",&n,&m);
    for(uint i=0;i<n;i++)scanf("%u",Val+i);
    for(uint i=1;i<n;i++)
    {
        uint u,v;scanf("%u%u",&u,&v);
        Way[--u].push_back(--v);
        Way[v].push_back(u);
    }
    dfs(0);
    for(uint i=0;i<n;i++)add(i,Val[i]);
    // for(uint i=0;i<n;i++)printf("%u\n",find(i,1));
    uint ans=0;
    while(m--)
    {
        uint op,u,v;
        scanf("%u%u%u",&op,&u,&v),u^=ans,v^=ans;
        if(op){u--;add(u,v-Val[u]);Val[u]=v;}else printf("%u\n",ans=find(u-1,v));
    }
    fflush(stdout);
    return 0;
}