点分治
点分治用于求解树上路径有关的问题。
其具体思想，对于当前处理的这一个分治区域，我们计算所有区域内跨过分治中心这一个点的所有路径的贡献，然后将分治中心及与其相邻的边删去，对于剩下的每一个分治区域再分别进行计算。
时间复杂度
看起来很暴力，实际上非常优秀，其关键就是我们对于分治中心的选取。一般而言，我们选择这一分治区域的重心。
选择重心的原因是，删去重心后，剩下的没一个区域内的点数至少减半，这样的话，最多只会递归 \(\log n\) 次，时间复杂度就是每一层处理的时间复杂度乘上 \(\log n\) 。
具体做法
模板题 P4178 Tree
询问树上两点距离小于等于 \(k\) 的点对数量。
对于当前处理的分治区域，从分治中心开始进行 \(dfs\) ，处理出每个结点到达中心的距离，并排序，然后双指针扫过去就可以了。
- 这样处理会有一个问题：有一些不合法的情况也会被计算在内。
如下图
因此我们考虑减去这样的不合法的情况，我们发现不合法是由于两个端点来自于同一个儿子，那么我们对于中心的每一个儿子，减去其所造成的不合法的贡献即可。
点击查看代码
inline void Getroot(int x,int f) {
sz[x]=1;
int now=0;
for(int i=hd[x],y;i;i=ne[i])
if(!vis[y=to[i]] && y!=f)
Getroot(y,x), sz[x]+=sz[y], now=max(now,sz[y]);
now=max(now,all-sz[x]);
if(now<Mx) Mx=now, Rt=x;
}
inline void Getdist(int x,int f,int dist) {
sz[x]=1; tmp[++cnt]=dist;
mx[Rt]=max(mx[Rt],dist);
dis[x][cnt[x]]=dist; cnt[x]++;
for(int i=hd[x],y;i;i=ne[i])
if(!vis[y=to[i]] && y!=f) Getdist(y,x,dist+1), sz[x]+=sz[y];
}
inline void Solve(int x) {
vis[x]=1;
for(int i=hd[x],y;i;i=ne[i]) if(!vis[y=to[i]]) {
Mx=inf; all=sz[y]; Getroot(y,0);
Getdist(Rt,0,0); New(Rt,mx[Rt],mx[x]);
Fa[Rt]=x; Solve(Rt);
}
}
inline int calc(int x,int dist0) {
cnt=0;
Getdist(x,dist0);
sort(tmp+1,tmp+1+cnt);
int l=1,r=cnt,res=0;
while(l<r)
if(tmp[l]+tmp[r]<=k) ret+=r-l, l++;
else r--;
return res;
}
点分树
点分树就是将每一个分治中心，向它所在区域内的下一级分治中心连边，由于每次选取的分治中心是重心，那么树高不会超过 \(\log n\) ，这样我们每一次就可以暴力在树上进行查询和修改等操作。
具体的，对于每一个结点，维护两个信息：
T1[x] // 点分树上 x 子树内的点到 x 的距离
T2[x] // 点分树上 x 子树内的点到 Fa[x] 的距离
// Fa[x] 是 x 在点分树上的父亲结点
// 一般的，将距离做下标
- 查询操作
对于 \(p\) 到 \(Rt\) 路径上的点 \(u\),上一次查询的点为 \(las\)
查询 \(T1[x]\) 内区间 \([0-(k-Dis[p][x])]\) 的贡献并加上。
查询 \(T2[las]\) 内区间 \([0-(k-Dis[p][x])]\) 的贡献并减去，因为这样的路径是不合法的。
- 修该操作
对于 \(p\) 到 \(Rt\) 路径上的点 \(u\)
在 \(T1[x]\) 中下标为 \(Dis[p][x]\) 的位置加上 \(v-a[p]\)
在 \(T2[x]\) 中下标为 \(Dis[p][Fa[x]]\) 的位置加上 \(v-a[p]\)。
开 \(vector\) 用树状数组维护即可。
点击查看代码
inline void New(int x,int v1,int v2) { T1.tree[x].resize(v1+2); T2.tree[x].resize(v2+2); }
inline void Getroot(int x,int f) {
sz[x]=1;
int now=0;
for(int i=hd[x],y;i;i=ne[i])
if(!vis[y=to[i]] && y!=f)
Getroot(y,x), sz[x]+=sz[y], now=max(now,sz[y]);
now=max(now,all-sz[x]);
if(now<Mx) Mx=now, Rt=x;
}
inline void Getdist(int x,int f,int dist) {
sz[x]=1;
mx[Rt]=max(mx[Rt],dist);
dis[x][cnt[x]]=dist; cnt[x]++;
for(int i=hd[x],y;i;i=ne[i])
if(!vis[y=to[i]] && y!=f) Getdist(y,x,dist+1), sz[x]+=sz[y];
}
inline void Solve(int x) {
vis[x]=1;
for(int i=hd[x],y;i;i=ne[i]) if(!vis[y=to[i]]) {
Mx=inf; all=sz[y]; Getroot(y,0);
Getdist(Rt,0,0); New(Rt,mx[Rt],mx[x]);
Fa[Rt]=x; Solve(Rt);
}
}
inline void Build(int p) {
int x=p,las=0,tmp=0;
while(x) {
T1.Modify(x,dis[p][tmp]+1,a[p]);
if(Fa[x]) T2.Modify(x,dis[p][tmp+1]+1,a[p]);
tmp++; x=Fa[x];
}
}
inline void Change(int p,int v) {
int x=p,tmp=0;
while(x) {
T1.Modify(x,dis[p][tmp]+1,v-a[p]);
if(Fa[x]) T2.Modify(x,dis[p][tmp+1]+1,v-a[p]);
tmp++; x=Fa[x];
}
a[p]=v;
}
inline int Ask(int p,int k) {
int res=0,x=p,tmp=0,las=0;
while(x) {
if(k>=dis[p][tmp]) res+=T1.Query(x,k-dis[p][tmp]+1);
if(las && k>=dis[p][tmp]) res-=T2.Query(las,k-dis[p][tmp]+1);
tmp++; las=x; x=Fa[x];
}
return res;
}
待更。
标签：tmp,sz,int,分治,T2,笔记,学习,now From： https://www.cnblogs.com/oscaryangzj/p/16845797.html