？！块块！？
为什么全是点分树？太无聊了。
点分树模板怎么能用点分树做呢？
而且点分树太菜了，稍微复杂一点的邻域问题比如邻域最大独立集就做不了了（也可能是我太菜了）。
哪有没有通用的方法呢？有的，树分块！具体来说，是 top cluster 树分块。
具体来说，它就是在树上选
-
定义虚树上的点为界点，记两个相邻的界点中浅的那个为上界点，深的为下界点，上节点与下节点间的路劲为簇路径。那么在上界点的子树内，下界点子树外的树上的节点数量与簇路径为
O(\frac{n}{B}) 。 -
任意一个非界点唯一对应了一对上界点和下界点。
怎么构建呢？先强令根节点为一个界点，然后记录当前未归类的点，如果
:::success[构建]
struct top_cl
{
int near,up,down;
//分别为距离最近的簇路劲上的点，上界点，下界点
}cl[N];
vector<int>bn,asup[N];//bn 存界点，asup 为一个点作为上界点的块的下界点集合。
vector<int>all[N];//在下节点处存储块内节点（不包括界点）
int ls[N],len;//临时储存要加如的点
bool vis[N];//标记一个点是否为界点
inline void link(int x,int y)//以 x 为界点，y 为下界点加块
{
if(!y) y=ls[len],bn.push_back(y);//y=0 代表一个子树为一块，那么随便选即可。
asup[x].push_back(y);//加入
cl[x].near=x;
for(int v=y;v!=x;v=fa[v]) cl[v].near=v;//簇路劲上直接赋值。
for(int i=1;i<=len;i++)
{
int v=ls[i];
cl[v].up=x,cl[v].down=y;
int j=v;
for(;!cl[j].near;j=fa[j]);//遍历找最近的簇路径
cl[v].near=cl[j].near;
if(v!=y)all[y].push_back(v);//加入
}
len=0;
}
int st[N],top,lsttop[N];//st 子树内的点 lsttop 配合 st 便利子树
int lstbn[N],wait[N];//lstbn 子树内上一个界点 wait 当前还没有加入的点的数量
inline void build(int x)
{
lsttop[x]=top;//记录先前
wait[x]=1;
int tot=0;
for(int v:edge[x])
{
if(v==fa[x])continue;
fa[v]=x;
st[++top]=v;
build(v);
wait[x]+=wait[v];
if(lstbn[v])//存在界点
{
lstbn[x]=lstbn[v];
tot++;
}
}
if(wait[x]>B||tot>1||!fa[x])//要加入的 >B 或有多个界点，此时它一定要是界点或为根
{
wait[x]=0;
lstbn[x]=x;
if(x!=1)bn.eb(x);//插入界点
vis[x]=1;
int j=lsttop[x]+1,now_down=0;
tot=0;edge[x].eb(-1);
for(int v:edge[x])
{
if(v==fa[x])continue;
if(v==-1||tot+wait[v]>B||(now_down&&lstbn[v]))//如果便利完了或 >B 了或有要用的下界点了就要加块了
{
for(;(v==-1||j<lsttop[v])&&j<=top;j++)ls[++len]=st[j];//将要归类的点压入
link(x,now_down),tot=now_down=0;
}
tot+=wait[v];
if(lstbn[v])now_down=lstbn[v];
}
edge[x].pop_back();
top=lsttop[x];
}
}:::
构建完后我们直接在每个块的上下界点处记录
考虑查询，块内直接插，然后就枚举其他块，对于当前块判断哪个界点距查询点近，那么就是查询点到块内点的必经点。
最后查询界点即可。
如果查询点就是界点也是一样的。
时间复杂度用
:::success[code]
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=1e5+7;
vector<int>edge[N];
namespace trLCA
{
#define B 32
int n0,a[N],s[N],t[N],b[N/B],f[20][N/B];
inline int Q(int l,int r)
{
if(l==r)return b[l];
int k=__lg(l^r);
return min(f[k][l],f[k][r]);
}
inline int query(int l,int r)
{
int x=l>>5,y=r>>5;
if(x==y)
{
int res=1e9;
for(int i=l;i<=r;i++)res=min(res,a[i]);
return res;
}
if(y-x==1)return min(t[l],s[r]);
return min({t[l],s[r],Q(x+1,y-1)});
}
inline void build(int n)
{
for(int l=0;l<n;l+=B)
{
int r=min(l+B,n)-1;
s[l]=a[l],t[r]=a[r];
for(int i=l+1;i<=r;i++)s[i]=min(s[i-1],a[i]);
for(int i=r-1;i>=l&&~i;i--)t[i]=min(t[i+1],a[i]);
}
n0=n>>5;
for(int i=0;i<n0;i++)f[0][i]=b[i]=t[i*B];
for(int i=1,j=2;j<n0;i++,j<<=1)
{
for(int l=0;l<n0;l+=j<<1)
{
int m=min(l+j,n0),r=min(l+(j<<1),n0);
f[i][m]=b[m],f[i][m-1]=b[m-1];
for(int k=m;k<r-1;k++)f[i][k+1]=min(f[i][k],b[k+1]);
for(int k=m-1;k>l;k--)f[i][k-1]=min(f[i][k],b[k-1]);
}
}
}
#undef B
int dfn[N],rk[N],ip,dep[N];
inline void dfs(int x,int fa)
{
a[ip]=dfn[fa];
dfn[x]=++ip;
rk[ip]=x;
for(int v:edge[x])
{
if(v==fa) continue;
dep[v]=dep[x]+1;
dfs(v,x);
}
}
inline void init(int n,int rt=1)
{
dep[rt]=0;
dfs(rt,0);
build(n);
}
inline int LCA(int x,int y)
{
if(x==y)return x;
if((x=dfn[x])>(y=dfn[y])) swap(x,y);
return rk[query(x,y-1)];
}
inline int getdis(int x,int y,int l=-1)
{
if(l==-1)l=LCA(x,y);
return dep[x]+dep[y]-2*dep[l];
}
}
using trLCA::LCA;
using trLCA::getdis;
const int B=700;
int n,m;
int fa[N],a[N];
struct top_cl
{
int fa,near,up,down;
}cl[N];
vector<int>bn,asup[N];
vector<tuple<int,int,int>>all[N];
int ls[N],len;
bool vis[N];
inline void link(int x,int y)
{
if(!y) y=ls[len],bn.push_back(y);
asup[x].push_back(y);
cl[y].fa=x;
cl[x].near=x;
for(int v=y;v!=x;v=fa[v]) cl[v].near=v;
for(int i=1;i<=len;i++)
{
int v=ls[i];
cl[v].up=x,cl[v].down=y;
int j=v;
for(;!cl[j].near;j=fa[j]);
cl[v].near=cl[j].near;
if(v!=y)all[y].push_back({v,getdis(v,y,cl[v].near),getdis(v,x,x)});
}
len=0;
}
int st[N],top,lsttop[N];
int lstbn[N],wait[N];
inline void build(int x)
{
lsttop[x]=top;
wait[x]=1;
int tot=0;
for(int v:edge[x])
{
if(v==fa[x])continue;
fa[v]=x;
st[++top]=v;
build(v);
wait[x]+=wait[v];
if(lstbn[v])
{
lstbn[x]=lstbn[v];
tot++;
}
}
if(wait[x]>B||tot>1||!fa[x])
{
wait[x]=0;
lstbn[x]=x;
if(x!=1)bn.eb(x);
vis[x]=1;
int j=lsttop[x]+1,now_down=0;
tot=0;edge[x].eb(-1);
for(int v:edge[x])
{
if(v==fa[x])continue;
if(v==-1||tot+wait[v]>B||(now_down&&lstbn[v]))
{
for(;(v==-1||j<lsttop[v])&&j<=top;j++)ls[++len]=st[j];
link(x,now_down),tot=now_down=0;
}
tot+=wait[v];
if(lstbn[v])now_down=lstbn[v];
}
edge[x].pop_back();
top=lsttop[x];
}
}
vector<int>dis[2][N];
int pos[N];
inline void update(int x)
{
int L=cl[x].down;
int id=pos[L],lst=0;
if(!dis[0][id].size())
{
int Max=0;
for(auto [v,d1,d2]:all[L])
Max=max({Max,d1,d2});
dis[0][id].resize(Max+1);
dis[1][id].resize(Max+1);
}
else
{
for(int&v:dis[0][id])v=0;
for(int&v:dis[1][id])v=0;
}
for(auto [v,d1,d2]:all[L])
{
dis[0][id][d1]+=a[v];
dis[1][id][d2]+=a[v];
}
lst=0;for(int&v:dis[0][id])v+=lst,lst=v;
lst=0;for(int&v:dis[1][id])v+=lst,lst=v;
}
bool vis1[N],vis2[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
edge[x].eb(y);
edge[y].eb(x);
}
trLCA::init(n);
build(1);
for(int i=0;i<(int)bn.size();i++)
pos[bn[i]]=i+1;
vis1[1]=1;
for(int v:bn)
vis1[v]=1,update(v);
int lstans=0;
while(m--)
{
int opt,x,d;
cin>>opt>>x>>d;
x^=lstans,d^=lstans;
if(opt==0)
{
int ans=0;
if(vis1[x])
{
if(x!=1)ans=dis[0][pos[x]][min(d,(int)dis[0][pos[x]].size()-1)];
vis2[x]=1;
for(int v:asup[x])
{
vis2[v]=1;
int id=pos[v];
ans+=dis[1][id][min(d,(int)dis[1][id].size()-1)];
}
for(int v:bn)
{
int d1=getdis(v,x);
if(d1<=d)
ans+=a[v];
if(vis2[v])continue;
int kl=v;
int kr=cl[v].up;
int d2=getdis(kr,x);
int id=pos[kl];
int lim=0,op=0;
if(d1<d2)lim=d-d1,op=0;
else lim=d-d2,op=1;
if(lim>=0)ans+=dis[op][id][min(lim,(int)dis[op][id].size()-1)];
}
if(getdis(x,1,1)<=d)ans+=a[1];
cout<<ans<<'\n';
lstans=ans;
vis2[x]=0;
for(int v:asup[x])
vis2[v]=0;
continue;
}
int L=cl[x].down;
for(auto [v,aa,bb]:all[L])
if(getdis(x,v)<=d)
ans+=a[v];
for(int v:bn)
{
int d1=getdis(v,x);
if(d1<=d)
ans+=a[v];
if(v==L)continue;
int kl=v;
int kr=cl[v].up;
int d2=getdis(kr,x);
int id=pos[kl];
int lim=0,op=0;
if(d1<d2)lim=d-d1,op=0;
else lim=d-d2,op=1;
// cout<<lim<<'\n';
// if(lim>0)cout<<"-->"<<op<<' '<<dis[op][id][min(lim,(int)dis[op][id].size()-1)]<<'\n';
if(lim>=0)ans+=dis[op][id][min(lim,(int)dis[op][id].size()-1)];
}
if(getdis(x,1,1)<=d)ans+=a[1];
cout<<ans<<'\n';
lstans=ans;
}
else
{
a[x]=d;
if(vis1[x]||x==1)continue;
update(x);
}
}
}:::
效率大概是点分树的一半.
优势
首先最大的优势就是支持任意可合并信息。
然后就是空间线性！但在本题没有体现出优势。
更多？
本题似乎可以做到单