前言
还真没有。
点分树
点分树是个神秘的东西。
点分树是通过更改原树形态使树的层数变为稳定 \(\log n\) 的一种重构树。
常用于解决与树原形态无关的带修改问题。
是这样的，有些树上问题，看起来用别的树形结构做不了，点分治能做。
但是它不仅多次询问（\(n\) 同级），还带修，有时候甚至强制在线，点分治直接去世了！
这个时候，当问题又跟树的形态关系不算很大时候（说完全无关也不可能是吧），点分树登场。
它提前做一遍点分治，建立一棵重构树，然后每次询问直接在这颗树上搞就行了。
树的建法
其实很简单，把点分治每轮的重心连起来就行了。
（比如说第一轮选中重心，分成很多个子树递归求解，每个子树的重心都向原重心连边，这样做下去就行了）
容易发现这样做完后，树的形态和原树大相径庭，但是它仍有 3 条重要性质：
-
树高 \(O(\log n)\) 级别，意味着很多暴力算法在这棵树上做复杂度也是 \(O(n\log n)\) 的。
-
两点点分树上的 lca 必然存在于两点原树路径上。
-
每个点的子树正式点分治算法时候它的子树。
简单运用
那么具体有什么用？我们看一道例题：
一棵树，单点修改，查询所有到某点距离小于等于某个值的点权值和，多次询问，强制在线。
先考虑不带修改，单次询问，此时可以使用暴力点分治，每次问一个子树内距离根（指重心）小于等于某个数的点求和，注意有不少的子树根本不用进去，在大的子树算完后只需要进入那个点所在的子树就行了，注意要把这个子树刚刚计算的答案（错误的答案）容斥掉。
好的带上多测之后，发现我在询问“子树内距离根（指重心）小于等于某个数的点求和”时候，子树变化很小，每次暴力算太愚蠢了。
那么我们能不能把这个结果预处理一下？可以的。
事实上，我们对于每个点都开一个值域线段树，上面存好子树内所有点到根的距离对应的和，然后询问的话直接查询一个前缀和就好了。
考虑容斥时候，减去的那个子树的计算是按到上一级重心的距离，但是到上一级重心又属于这个子树的已经在上面的线段树里打乱了，没法调出来单独求和。
咋办？每个点多开一个线段树存储上一级就行了。
修改的话，这个点到点分树的跟路径上都要修改，改动它们的两棵线段树。
注意：点分树的形态和原树大相径庭，故距离的变化并不是单调的，要经常性的求树上两点的距离，实现要求不精细直接倍增即可，要求精细就写个 dfs 序来 \(O(1)\) 查询（也存在直接存储的做法，不过我懒得搞了）。
以下是非常史的本题 AC 代码。
注释过几天加上。
#include<bits/stdc++.h>
using namespace std;
#define N 114514
int vis[N],a[N];
vector<int> e[N];
int sz[N],mxs[N],rt;
vector<int> col[N];
//LCA
int d[N],f[N][20];
void dfs(int u)
{
for(int i=1;(1<<i)<=d[u];i++) f[u][i]=f[f[u][i-1]][i-1];
for(auto v:e[u]) if(v!=f[u][0])
d[v]=d[u]+1,f[v][0]=u,dfs(v);
}
int dis(int xx,int yy)
{
if(d[xx]<d[yy]) swap(xx,yy);
int x=xx,y=yy;
for(int i=17;i>=0;i--) if(d[f[x][i]]>=d[y]) x=f[x][i];
if(x==y) return d[xx]-d[x];
for(int i=17;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
int lca=f[x][0];
return d[xx]+d[yy]-2*d[lca];
}
//Sgt
const int maxx=99999;
int tot,root[N][2];
int ls[N*100],rs[N*100],val[N*100];
#define mid ((l+r)>>1)
void change(int &o,int l,int r,int x,int v)
{
if(!o) o=++tot;
val[o]+=v;
if(l==r) return;
if(x<=mid) change(ls[o],l,mid,x,v);
else change(rs[o],mid+1,r,x,v);
}
int ask(int o,int l,int r,int al,int ar)
{
if(ar<0) return 0;
if(al<=l&&r<=ar) return val[o];
int ans=0;
if(ar>mid) ans+=ask(rs[o],mid+1,r,al,ar);
if(al<=mid) ans+=ask(ls[o],l,mid,al,ar);
return ans;
}
int d1[N];
void dfs1(int u,int fa,int n)
{
sz[u]=1;mxs[u]=0;
for(auto v:e[u]) if(!vis[v]&&v!=fa) dfs1(v,u,n),sz[u]+=sz[v],mxs[u]=max(mxs[u],sz[v]);
mxs[u]=max(mxs[u],n-sz[u]);
if(mxs[u]<=mxs[rt]) rt=u;
}
void dfs2(int u,int d,int fa)
{
if(d1[u]!=-1) change(root[rt][1],0,maxx,d1[u],a[u]);
change(root[rt][0],0,maxx,d,a[u]);
d1[u]=d;
for(auto v:e[u]) if(v!=fa&&!vis[v]) dfs2(v,d+1,u);
}
int dfroot,dffa[N];
void solve(int r,int n,int lastrt)
{
rt=0;mxs[0]=998244353;
dfs1(r,0,n);
int rooooot=rt;
dffa[rt]=lastrt;
change(root[rt][0],0,maxx,0,a[rt]);
if(d1[rt]!=-1) change(root[rt][1],0,maxx,d1[rt],a[rt]);
for(auto v:e[rt]) if(!vis[v]) dfs2(v,1,rt);
vis[rt]=1;
for(auto v:e[rt]) if(!vis[v])
{
if(sz[v]<sz[rt]) solve(v,sz[v],rt);
else solve(v,n-sz[rt],rooooot);
}
dfroot=rooooot;
}
int query(int x,int k)
{
int ans=0,ok=k,xx=x;
while(x!=dfroot)
{
ans+=ask(root[x][0],0,maxx,0,k)-ask(root[x][1],0,maxx,0,ok-dis(xx,dffa[x]));
x=dffa[x];
k=ok-dis(xx,x);
}
return ans+ask(root[x][0],0,maxx,0,k);
}
void modify(int x,int y)
{
int zl=y-a[x];
a[x]=y;
int xx=x;
while(x!=dfroot)
{
change(root[x][0],0,maxx,dis(xx,x),zl);
change(root[x][1],0,maxx,dis(xx,dffa[x]),zl);
x=dffa[x];
}
change(root[x][0],0,maxx,dis(xx,x),zl);
}
int n,q,lastans;
int main()
{
memset(d1,-1,sizeof(d1));
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
int u,v;
for(int i=1;i<n;i++) cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
dfs(1);
solve(1,n,0);
while(q--)
{
int op,x,y;
cin>>op>>x>>y;x^=lastans,y^=lastans;
if(op==0)
{
lastans=query(x,y);
cout<<lastans<<endl;
}
else modify(x,y);
}
return 0;
}