卍点分制详解,附例题。

发布于 2018-09-19  1345 次阅读


点分治一般都是处理树上路径用的。
比如问你树上距离为x的点对有多少个?
之类的。

按照传统惯例,本文从是什么,为什么,做么做三个方面讲解。

1.点分治是什么

字面意思。
对树上的点进行分治。
考虑刚开始的问题,树上距离为x的点对有多少个?

我设现在对点k进行点分治。
距离为x的点对关于k只有两种位置。
设点对为(a,b)
一个是a->b经过k,一个是不经过。
经过的显然可以求出,不经过的可以递归求解。(具体在怎么做里面有)

2.为什么点分治可以省时间

显然对于刚才的问题,一个显然的暴力是O(n^2)枚举点对*O(n)dfs求距离
优秀的O(n^3)做法。

什么?你竟然会O(n^2logn)的做法?
先做出每个点到根的距离,再枚举点对求lca。
优秀的O(n^2logn)做法。

出题人:\'不行,这做法太水,我往数据范围后加个0\'
n<=50000;

???
抱歉,我会点分治,O(nlog2n)
找点进行递归,层数不超过
O(logn)(后面解释),dfs求距离O(n)胡乱统计答案O(logn)(后面解释)

3.怎么做

上面的当废话看就行。(其实你直接就看这了,是不是(#滑稽))

显然,点分治肯定要找一个点,那么这个点选哪个?
假如我们的树退化成了链,
每次递归选链首显然是要递归O(n)次
如果我选链心,就是O(logn)次。

如果选点后子树越大,递归层数越多,时间越慢,反之则越快。

那么问题来了?

3. 1怎么求重心。

重心的O(n)求法。

考虑什么样的点会成为重心。

根据定义,以重心为根的所有子树中最大的子树节点数最小。

所以我们肯定要求出每个点周围所有子树的大小。
儿子的好求,父亲所在子树大小怎么求?
我再dfs一遍?

树的大小-所有儿子大小即可。

首先声明一下变量。

siz[x] 表示以x为根子树大小(包括x)
mxson[x] 表示x的所有子树中最大的子树大小(不包括x,就是x周围一圈子树中最大的)
root 表示重心
mxer 表示当前树的大小。

然后是代码,根据上面定义写dfs就行,好写。

inline void getroot(int x,int fa)  
{  
 siz[x]=1,mxson[x]=0;  
 for(int i=alist[x];i;i=edge[i].nxt)  
 {  
 int v=edge[i].v;  
 if(vis[v]||v==fa) continue;  
 getroot(v,x);  
 siz[x]=siz[x]+siz[v];  
 mxson[x]=max(mxson[x],siz[v]);  
 }  
 mxson[x]=max(mxson[x],mxer-siz[x]);  
 if(mxson[x]<mxson[root]) root=x;  
}

<

pre>
然后我们进行点分治,一般会有3个函数,

分别为

1. dfs求路径长

2. cal统计合法路径

3. divide对树进行点分治。

....

其他的函数基本上是套一些数据结构或什么优化统计。

下面以[luogu4178]Tree的代码为例

题目大意:

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

首先是divide函数

inline void divide(int tmroot)  
{  
 deep[tmroot]=0;//tmroot是每次分治树的重心  
 ans=ans+cal(tmroot);//对tmroot所在子树统计答案  
 vis[tmroot]=true;//vis数组用来划分子树,防止被重复计算  
 for(int i=alist[tmroot];i;i=edge[i].nxt)  
 {  
 int v=edge[i].v;int val=edge[i].val;  
 if(vis[v]) continue;  
 deep[v]=val;  
 ans=ans-cal(v);//根据题目的不同统计也不同  
 //这题我用容斥去重,其实dp也行  
 //为什么会重可以看我的cal函数  
 MX=INF;root=0;mxer=soz[v];  
 getroot(v,0);//往下递归点分治,最多log层  
 divide(root);  
 }  
 return ;  
}

cal函数

inline int cal(int st)  
{  
 poi=0;dfs(st,0);//求以st为根子树中每个点到st的距离  
 sort(sum+1,sum+1+poi);  
 int l=1,r=poi,nmbd=0;  
 while(l<r)//本题让求距离小于等于x的点对,排序后双指针就行。  
 {  
 if(sum[l]+sum[r]<=k) nmbd+=r-l,l++;  
 else r--;  
 }//显然会有重复的,比如说在两个点都在同一子树中  
 //我们点分治是统计路径过分治点的点对个数;  
 return nmbd;  
}

<

pre>
dfs函数

inline void dfs(int x,int fa)  
{  
 sum[++poi]=deep[x];  
 for(int i=alist[x];i;i=edge[i].nxt)  
 {  
 int v=edge[i].v;int val=edge[i].val;  
 if(v==fa||vis[v]) continue;  
 deep[v]=deep[x]+val;  
 dfs(v,x);  
 }  
}

大概就是这样了,根据题的不同把cal函数改改就行。
最后推荐几道cf好题。
CF293E,简单题
CF715C,稍微加了点数论的好题

由于本人水平很菜,如果文章有错误可以留言指出。
如有不懂之处,也可留言。

3.00 avg. rating (71% score) - 2 votes

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。