点分治

好久都没有搞博客了，还是决定来一篇的好，主要是自己学的时候有点自闭，希望能帮助到其他人 那么开始了 ------------ 点分治最简单的应用是：对于一棵树，统计长度为 $x$ 的路径的路径数 当然点分治还有其他的有趣的应用，但我们先从最简单的开始 对于这一类问题，最暴力的做法是 $n^2$ 枚举点然后计算距离，复杂度在 $n^2$ $log_2^n$ 到 $n^3$ ，这显然不够优秀，而使用点分治可以将复杂度降到 $n$ $log_2^n$ 左右（这里我是胡说的，我也不知道，总之降了不少） 接下来的逻辑可能有点乱。 点分治的过程大概分这样几步：**找到一个点为根，统计答案，然后将它的子树分离，分别进行同样的操作，继续，直到只剩下一个点。** 伪代码大概就是这样 ```cpp void solve(int x){//进行分治的函数，x为根 work();//统计答案/进行操作 v[x]=1;//将这个点去掉，将整棵树分成几个子树 for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]) continue; root=0; getroot(y);//为这棵子树找到一个新的根 solve(root)； } } ``` 这个过程应该跟其他分治的思想差不多 其中选择的根是有要求的，为了保证时间复杂度，我们需要尽量的让子树的大小相近，所以每一次我们选择的根都最好是当前这棵树的重心 **树的重心：树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。** 简单的 $o(n)$ 跑一遍就可以找到树的重心了 ```cpp void geiroot(int x,int fa){ son[x]=0;//记录最大的儿子的size size[x]=1;//记录本身子树的size for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(y==fa || v[y]) continue; //v[y]=1表示这个点是删除掉的，即用来分开几棵子树的，所以不能继续 dfs(y,x); size[x]+=size[y]; son[x]=max(son[x],size[y]); } son[x]=max(son[x],sum-size[x]);//sum是当前子树的大小 if(son[x]<son[root]) root=x;//比较一下就可以找到当前子树的重心root了 } ``` 不知道你会不会有这个问题，我知道要把一棵树不断进行分治，也知道每次分治的点要找树的重心，但我为什么要这么做，我这么做是在干什么？ 我之前说我逻辑混乱就在这里了，别着急就在下面 对于一棵已经确定了根的树，我们可以将这棵树上的所有边简单的分为两类，经过根节点的和不经过根节点的。对于不经过根节点的边，一定只存在于某一棵子树之中，我们可以通过分治该子树进行统计，所以我们需要解决的是统计经过根节点的边。 这就是我们的 work 函数了，也是点分治中灵活变换的一部分，通过改变这部分就可以取解决很多其他题目。而且你会发现前面的基本没有难度，难度都在后面。 看起来我们可以直接求出当前子树中每个点到根节点的距离然后直接计算，但是这样忽视了一种情况：如果这两个点在同一个子树中，那么这就不是他们之间的距离。 我们考虑如何去掉这种情况，这也是我觉得点分治最难的地方。 我们先从最简单的第一道例题开始，[第一道例题](https://www.luogu.org/problemnew/show/CF161D) 这道题需要我们求出来长度为 $k$ 的路径的数量，这里提供一种做法 ```cpp int ans; int cnt[2002],tmp[2002]; //cnt 记录的是已知的长度为 x 的边有多少条 //tmp 是当前这棵子树中长度为 x 的边有多少条 void dfs(int x,int fa,int dep){ if(dep<=m){ ans+=cnt[m-dep]; //因为 cnt 里的数据不包含本棵子树里的数据，这样就能避免错误情况 tmp[dep]++;//记录一下，以便统计完这棵子树后加上 } for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]==0 && y!=fa){ dfs(y,x,dep+1); } } } void work(int x){ memset(cnt,0,sizeof(cnt));//清一下 int res=0; cnt[0]=1;//边的一个端点可以是根节点自己 for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]) continue; memset(tmp,0,sizeof(tmp));//清一下 dfs(y,0,1); for(int j=0;j<=m;j++){//将这棵子树的信息加到已知信息中 cnt[j]+=tmp[j]; } } } void solve(int x){//分治的过程上面已经说过了 v[x]=1; work(x); for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]) continue; root=0; size[root]=sum=size[y];//更新当前子树的大小 getroot(y,0); solve(root); } } ``` 这种做法适用于 $k$ 很小的情况，下面这道题也可以用这种方法完成，[第二道例题](https://www.luogu.org/problemnew/show/P2634) 这道题是要求求出所有长度为 $3$ 的倍数的边（包括0），因为他没说边权范围，所以不能直接硬做，但我们可以直接给边权一直 %$3$ ，具体操作如下 ```cpp void dfs(int x,int fa,int dep){ dep%=3;//边权模3 if(dep==0) ans+=cnt[0]; if(dep==1) ans+=cnt[2]; if(dep==2) ans+=cnt[1]; //根据不同情况统计答案，这个应该好理解吧 tmp[dep]++; for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]==0 && y!=fa){ dfs(y,x,dep+w[i]); } } } void work(int x){ memset(cnt,0,sizeof(cnt)); int res=0; cnt[0]=1; for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]) continue; memset(tmp,0,sizeof(tmp)); dfs(y,0,w[i]); for(int j=0;j<=2;j++){ cnt[j]+=tmp[j]; } } } ``` 这样做的话要记得答案要乘2，因为那道题边是双向的，而且最后还要加上每个点到自己。 这种做法是通过避免统计同一子树里的点来保证正确性的，下面还有一种方法，是通过删去错误的统计来保证正确性的。同样是聪聪可可那道题。 ```cpp void getdeep(int x,int fa){ t[d[x]]++; for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(y==fa || v[y]==1) continue; d[y]=(d[x]+w[i])%3; getdeep(y,x); } } int work(int x,int v){ t[0]=t[1]=t[2]=0;//t记录长度为 x 的边数 d[x]=v; getdeep(x,0);//计算边的长度 return t[1]*t[2]*2+t[0]*t[0];//这个显然吧 } void solve(int x){ ans+=work(x,0);//在这里统计了所有的情况 v[x]=1; for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]) continue; ans-=work(y,w[i]);//在这里减去了同一棵子树的情况 //因为x已经被打了标记，这样只会遍历到某一棵子树里的所有点 //记得算上 x-y 这条边的边权 root=0; size[root]=sum=size[y]; dfs(y,0); solve(root); } } ``` 这种做法的思想是先计算后删去，同样保证了统计的正确性。 那么接下来我们再看一眼洛谷上的模板题，[洛谷模板题](https://www.luogu.org/problemnew/show/P3806) 这道题一次给了一堆 $k$ ，不过只要求你判断是否存在，并不要求去统计数量，但用原来的方法似乎也不好搞 我们可以用另一种方法来搞定他。 这个做法的大致思路如下：统计子树里的每个点，用结构体分别记录他离根节点的距离和它属于哪一棵子树，将这些点按照距离排序。接下来对于每个 $k$ ，先找到一个左端点 $l$ ，然后用二分查找找到第一个距离为 $k-i$ 的点，判断两个点是否在同一个子树中，如果在同一子树中则移动右端点直到符合题意或者没有其他距离为 $k-i$ 的点，具体实现可以看代码 ```cpp int search(int x){//正常的二分查找 int l=1,r=num,mid,ans; while(l<=r){ mid=l+r>>1; if(dis[mid].d<x) l=mid+1; else r=mid-1,ans=mid; } return ans; } void dfss(int x,int fa,int ww,int d){//将每个点记录下来 dis[++num]=(node){d,ww};//记录距离和属于哪一子树 for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y] || y==fa) continue; dfss(y,x,ww,d+w[i]); } } void work(int x){ num=0; for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(v[y]) continue; dfss(y,x,y,w[i]); } dis[++num]=(node){0,0}; sort(dis+1,dis+num+1,cmp);//按距离大小排个序 for(int i=1;i<=m;i++){ if(ans[i]) continue;//这里是一个剪枝 int l=1; while(l<num && dis[l].d+dis[num].d<a[i]) l++; while(l<num && !ans[i]){ if(a[i]-dis[l].d<dis[l].d) break;//不可能存在 int pot=search(a[i]-dis[l].d);//找到第一个 while(l<=num&&dis[pot].d+dis[l].d==a[i]&&dis[pot].w==dis[l].w) pot++;//在同一棵子树的话就右移右端点 if(dis[pot].d+dis[l].d==a[i]) ans[i]=1;//有的话统计答案 l++; } } } ``` 好吧说实话我不会算复杂度，这里只是在讲思路，你相信他是能过得就好了。 对于不同的题需要改的地方就是 work() 这里，根据不同的题意来进行不同的统计就好了，记得要去掉同一子树的情况 那么就扔一道作业题吧 [作业题](https://www.luogu.org/problemnew/show/P4149) 这道题要我们求出点最少的长度为 $k$ 的边，所以我们还需要记录深度，至于统计答案的方法以及去重的方法就需要琢磨了。 ------------ 据说很多点分治都可以用树形 $dp$ 做？等我回头研究一下再更新 ------------ 那么我拖了几个月（跨年了）的点分治的大坑终于是填了，我任务计划里的点分治也终于可以划掉了 开心，撒花 ------------ 19:2:20 更新一波树形dp解点分治的 其实都挺好想的，$f[i][j]$ 表示第 $i$ 个点为起点往下长度为 $j$ 的路径的条数，更新的时候注意不要重复计算就可以了 但这样复杂度是 $n*k$ 的，感觉还是点分治优一点？ 第一道例题的树形dp代码 ```cpp int f[50505][600]; void dfs(int x,int fa){ f[x][0]=1; for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(y==fa) continue; dfs(y,x); for(int j=0;j<=k;j++){ if(k-j-w[i]>=0) ans+=f[y][j]*f[x][k-j-w[i]]; } for(int j=0;j<=k;j++){ if(j-w[i]>=0){ f[x][j]+=f[y][j-w[i]]; } } } } int main(){ int n=read(); k=read(); for(int i=1;i<n;i++){ int x=read(),y=read(); add(x,y,1); add(y,x,1); } dfs(1,0); cout<<ans<<endl; return 0; } ``` 19:2:23 ### 动态点分治 学数据结构的时候发现有个东西叫做动态点分治，稍微微学习了下下 动态点分治主要是应用数据结构 通过对于点分治的学习，我们每次找树的一个重心，然后递归每个子树，这些找到的重心构成一个树形结构，我们叫它点分树，因为这个分治中心构成的树的深度$O( log_2^n )$，所以还是在每个分治中心维护一个数据结构，修改和查询都暴力跳就可以了 有点类似于树套树的感觉 就是将原图中的点排成一棵有根树，然后在每一个点上以距离为下标点值为权值开一棵线段树。简单来说就是对于 $x$ 号点的线段树中 $l=r=y$ 的结点，表示的是离该结点距离为 $y$ 的点权值之和 来让我们看一道例题 [一道例题](https://www.lydsy.com/JudgeOnline/problem.php?id=3730) 这道题要求的是单点修改和单点范围型查询，我们分布来分析 对于单点修改，我们不断向上追寻这个点的父节点，这里的父节点指的是点分树上的父亲而不是原树里的父亲，然后修改次父亲结点的线段树。操作如下。 ```cpp void modify(int &p,int l,int r,int x,int y){ if(p==0){ p=++cnt; } t[p].v+=y; if(l==r) return; int mid=l+r>>1; if(x<=mid) modify(t[p].l,l,mid,x,y); else modify(t[p].r,mid+1,r,x,y); } void premodify(int x,int y) { modify(rt[x],0,n-1,0,y); for (int i=x;fa[i];i=fa[i]) { int dist=getdis(x,fa[i]); modify(rt[fa[i]],0,n-1,dist,y); modify(rt[i+n],0,n-1,dist,y); } } ``` 这样我们就修改了所有比这个点深度浅的点的信息。为了防止计算重复，我们定义标号为 $i+n$ 的点同样表示 $i$ 的父亲，但只会收到来自 $i$ 的更新，这样可以防止我们统计 $i$ 的父亲的答案时重复计算。 对于统计答案，我们同样是向上追溯所有深度更浅的结点，判断两个点之间的距离，如果距离 $dis$ 小于等于 $k$，那么统计所有其结点距离为 $k-dis$ 的结点的距离，再进行一次去重。 代码如下 ```cpp int qsum(int x,int l,int r,int ql,int qr){ if(x==0) return 0; if(l>=ql && r<=qr) return t[x].v; int mid=l+r>>1,res=0; if(ql<=mid) res+=qsum(t[x].l,l,mid,ql,qr); if(qr>mid) res+=qsum(t[x].r,mid+1,r,ql,qr); return res; } int preqsum(int x,int y){ int res=qsum(rt[x],0,n-1,0,y); for(int i=x;fa[i];i=fa[i]){ int dist=getdis(x,fa[i]); if(y>=dist){ res+=qsum(rt[fa[i]],0,n-1,0,y-dist)-qsum(rt[i+n],0,n-1,0,y-dist); } } return res; } ``` 因为树的深度很浅，所以时间复杂度不是很高。至于这个为什么是对的，通过点分治就可以理解了。 但是我实际用起来还是不知道该怎么办。 又一道跟这道题正好反过来的题 [一道例题](https://www.lydsy.com/JudgeOnline/problem.php?id=4372) 理性理解吧