感觉可以理解为带修点分治。
常用于解决与树原形态无关的带修改问题。 —— oi-wiki
点分树是通过更改原树形态使树的层数变为稳定 \(\log n\) 的一种重构树。就是通过点分治找重心的方式，将这一层重心为上一层重心的儿子。
所以对于很多暴力的复杂度是正确的。
一开始发现建树错了，然后发现是原先的点分治错了，然后才知道其实错误的求重心也可能会有正确的复杂度
2023NOIP A层联测21 距离
子任务二可以直接拿点分树做，就是对于每个重心维护到这个点距离最近的点的距离。然后查询时就将重心看作 \(lca\)，直接暴跳就可以了。
点击查看代码
void find(int x,int f){
siz[x]=1;
mx[x]=0;
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==f || vis[y]) continue;
find(y,x);
siz[x]+=siz[y];
mx[x]=max(mx[x],siz[y]);
}
mx[x]=max(mx[x],S-siz[x]);
if(mx[root]>mx[x]) root=x;
}
void solve(int x){
vis[x]=1;
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(vis[y]) continue;
S=siz[y],root=0;
find(y,x);
fat[root]=x;
solve(root);
}
}
int mxxx[N];
void updata(int x){
for(int i=x;i;i=fat[i]){
int dis=ask_dist(i,x);
mxxx[i]=min(mxxx[i],dis);
}
}
int query(int x){
int ans=inf;
for(int i=x;i;i=fat[i]){
int dis=ask_dist(x,i);
if(mxxx[i]>(1ll<<50)) continue;
ans=min(ans,dis+mxxx[i]);
}
return ans;
}
然后考虑两对点，做法就是点分治套点分树，对 \(x,a\) 进行点分治，然后将在这一层的操作处理掉，按顺序对 \(y,b\) 进行点分树上的修改和查询。具体就是先建一棵点分树，然后将每个操作压入所有涉及到的分治重心上，这里直接在点分树上跳就可以，可以发现每个操作最多被处理 \(\log n\) 次。复杂度就是 \(O(n \log^2 n)\)
标签：重心,int,siz,分治,点分树,root,mx From： https://www.cnblogs.com/jinjiaqioi/p/17806380.html