点分治 & 动态树分治 & 树上启发式合并 学习笔记
树上点分治
点分治
考虑我们要在一棵树上统计有关路径、连通块、符合条件的点对等信息。
暴力地，对于每一个节点，搜一遍它子树内的所有节点统计答案，搜一次是 \(O(n)\) 的，总的就是 \(O(n^2)\) 的。
点分治优化这个暴力。考虑到我们要统计的信息与树的父子结构无关。则对于当前子树内的一条路径来说，它分为经过子树根节点，和不经过子树根节点两种情况。
我们只统计经过子树根节点的路径。
而其他的则递归向下处理。
当我们把当前子树根节点删掉以后，我们递归向下处理后的下一个子树根节点可以是它的连通块内的任意节点（可以不是当前根的儿子）。
于是我们考虑每次把连通块内的重心作为根节点，因为重心的子树大小不超过 \(n/2\)，这样每一层子树大小都除以 2。则时间复杂度为：
这里有一个模板实现：只需将 calc 和 dfs 内统计答案的部分具体题目具体实现即可。
注意有些题，如建虚树的题，虽然可以用点分治做，但是点分治的多次 dfs 统计答案和重心时间上的常数因子极大，须谨慎使用。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int tot,to[N<<1],nx[N<<1],st[N];
void add(int x,int y){
to[++tot]=y,nx[tot]=st[x],st[x]=tot;
}
int vis[N],sz[N],min1,as;
void dfs1(int x,int y){
sz[x]=1;
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y&&!vis[v])dfs1(v,x),sz[x]+=sz[v];
}
}
void dfs2(int rt,int x,int y){
int max1=sz[rt]-sz[x];
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y&&!vis[v])dfs2(rt,v,x),max1=max(max1,sz[v]);
}
if(max1<min1)min1=max1,as=x;
}
int zhong(int x){
dfs1(x,0);
min1=N;
dfs2(x,x,0);
return as;
}
void calc(int x,int y){
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y&&!vis[v]){
calc(v,x);
}
}
}
void dfs(int x){
x=zhong(x);
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(!vis[v]){
calc(v,x);
}
}
vis[x]=1;
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(!vis[v])dfs(v);
}
}
int n;
int main(){
dfs(1);
}
点分树
我们把搜到的一个重心和它的上一级重心连边（其上一级重心作为它的父亲），形成一个树状结构，就叫点分树，它的高度显然是 \(O(\log n)\)
点分树的性质1：点分树上两点 \(u,v\) 的 LCA 一定在原树 \(u\) 到 \(v\) 的路径上。其原理就是它们的 LCA 是先前的重心，它一定把 \(u\) 和 \(v\) 分到了两个连通块内，所以 LCA 一定在它们的路径上。
由性质1，我们可以得到性质2，\(dis\) 指原树上两点距离，LCA 为点分树上的最近公共祖先：
要注意点分树上的距离和原树没有任何关系！！！
点分树的性质3：由于点分树是点分治搜出来的，所以它的所有节点的子树大小和是 \(O(n\log n)\) 的。
动态点分治
点分治是离线的，如果要在线、修改、多次询问怎么办呢？
考虑在点分树上维护修改和询问信息，因为点分树是 \(O(\log n)\) 高的，所以我们可以暴力跳一个点的父亲进行维护。
例题 1
Luogu P6329 【模板】点分树 | 震波
题解
省流：大码量毒瘤题。
求（带修改）
由上面的性质（\(dis\) 为原树，\(LCA\) 为点分树）：
考虑先找 LCA，再确定 \(y\)。
则我们从 \(x\) 一直向上跳父亲，统计当前子树内深度小于等于某个值的点权和，深度是原树上的深度。 注意要去掉从 \(x\) 跳上来的那棵子树的重复贡献。
可以对每个节点开一个大小为子树高度动态开点线段树或树状数组。
为了去重需要维护两个值：
- \(u\) 子树内距离 \(u\) 小于等于 \(i\) 的点权和。
- \(u\) 子树内距离 \(fa_u\) 小于等于 \(i\) 的点权和 。
一定要注意点分树上的距离与原树上的距离无关。
修改也暴力跳父亲修改即可。
时间复杂度 \(O(m\log ^2n)\)
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=2e5+5;
int tot,to[N<<1],nx[N<<1],st[N];
void add(int u,int v){
to[++tot]=v,nx[tot]=st[u],st[u]=tot;
}
int sz[N],vis[N];
int dep[N],f[N][20];
void dfs1(int x,int y){
sz[x]=1;
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(!vis[v]&&v!=y)dfs1(v,x),sz[x]+=sz[v];
}
}
int min1,as;
void dfs2(int rt,int x,int y){
int max1=sz[rt]-sz[x];
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(!vis[v]&&v!=y)dfs2(rt,v,x),max1=max(max1,sz[v]);
}
if(max1<min1)min1=max1,as=x;
}
void dfs3(int x,int y){
f[x][0]=y,dep[x]=dep[y]+1;
for(int i=1;i<20;i++)f[x][i]=f[f[x][i-1]][i-1];
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y){
dfs3(v,x);
}
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=0,j=dep[x]-dep[y];j;j>>=1,i++)if(j&1)x=f[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int dis(int x,int y){
int l=lca(x,y);
return dep[x]+dep[y]-2*dep[l];
}
int zhong(int x){
dfs1(x,0);
min1=N;
dfs2(x,x,0);
return as;
}
int fa[N];
struct tree{
int lowbit(int x){
return x&(-x);
}
vector<int> s;
void update(int x,int y){
while(x<s.size())s[x]+=y,x+=lowbit(x);
}
int query(int x){
int sum=0;
if(x>=s.size())x=s.size()-1;
while(x>0)sum+=s[x],x-=lowbit(x);
return sum;
}
}tr1[N],tr2[N];
int dfs(int x){
x=zhong(x);
vis[x]=1;
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(!vis[v]){
fa[dfs(v)]=x;
}
}
return x;
}
int a[N],mx[N];
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
}
dfs3(1,0);
dfs(1);
for(int i=1;i<=n;i++){
int x=i;
while(x){
int d=dis(x,i);
mx[x]=max(mx[x],d);
x=fa[x];
}
}
for(int i=1;i<=n;i++){
tr1[i].s.resize(mx[i]+2);
if(fa[i])tr2[i].s.resize(mx[fa[i]]+2);
}
for(int i=1;i<=n;i++){
int x=i;
while(x){
int d=dis(x,i);
tr1[x].update(d+1,a[i]);
if(fa[x]){
d=dis(fa[x],i);
tr2[x].update(d+1,a[i]);
}
x=fa[x];
}
}
int lastans=0;
for(int i=1;i<=m;i++){
int opt,x,y;
cin>>opt>>x>>y;
x^=lastans,y^=lastans;
if(opt==1){
swap(a[x],y);
y=a[x]-y;
int z=x;
while(x){
int d=dis(x,z);
tr1[x].update(d+1,y);
if(fa[x]){
d=dis(fa[x],z);
tr2[x].update(d+1,y);
}
x=fa[x];
}
continue;
}
lastans=0;
int z=x,f=0;
while(x){
int d=dis(x,z);
if(d>y){
f=x,x=fa[x];
continue;
}
lastans+=tr1[x].query(y-d+1);
if(f)lastans-=tr2[f].query(y-d+1);
f=x,x=fa[x];
}
cout<<lastans<<endl;
}
}
例题 2
P2056 [ZJOI2007] 捉迷藏
P4115 Qtree4
下面是上面的加强版，也就是给定边权。
可以用堆维护点分树上 \(u\) 的子树内的点到 \(fa_u\) 的最长距离。
对于每个点，经过它的路径的最大值也可以用堆维护。
最终答案也可以用一个堆维护。
时间复杂度 \(O(Q\log ^2N)\)
树上启发式合并
我们要统计一个子树内的相关信息，如果对每个点都遍历一遍子树，则显然是 \(O(n^2)\) 的。
考虑由于父亲可以继承儿子的信息，于是可以减小时间消耗。
考虑对树进行重链剖分（树链剖分），在这里，我们只需要知道重儿子是谁即可。
考虑先统计所有轻儿子对答案的贡献，每次统计完就清空残留信息。
之后统计重儿子的贡献，注意不清空，而继承信息。
之后再把所有轻儿子的信息全部一并加上（不用再统计轻儿子的对答案的贡献，先前已经统计过）。
于是就可以统计当前子树内对答案的贡献
可以证明（我不会），如此的时间复杂度是 \(O(n\log n)\) 的。
要注意重儿子要算对，否则复杂度不正确。
下面是一个模板，把 add 和 del 内用于增减信息的操作结合题目修改，并在 dfs2 的结尾加入统计最终答案的代码。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int tot,to[N<<1],nx[N<<1],st[N],c[N];
void add(int x,int y){
to[++tot]=y,nx[tot]=st[x],st[x]=tot;
}
int sz[N],son[N];
void dfs1(int x,int y){
sz[x]=1;
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y){
dfs1(v,x);
sz[x]+=sz[v];
if(sz[v]>sz[son[x]])son[x]=v;
}
}
}
void add(int x){
x=c[x];
}
void del(int x){
x=c[x];
}
void dfs2(int x,int y){
add(x);
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y)dfs2(v,x);
}
}
void clear(int x,int y){
del(x);
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y)clear(v,x);
}
}
void dfs(int x,int y){
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y&&v!=son[x]){
dfs(v,x);
clear(v,x);
}
}
if(son[x])dfs(son[x],x);
add(x);
for(int i=st[x];i;i=nx[i]){
int v=to[i];
if(v!=y&&v!=son[x]){
dfs2(v,x);
}
}
}
int main(){
dfs1(1,0);
dfs(1,0);
}