注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

树的分治(点分治)  

2014-03-31 22:07:52|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我是看了以下这篇博客便恍然大悟的,写得太好了,我都不想写了,直接转:

处理此类树上满足某要求的路径问题,通常采用点分治的方法。

而对于每次处理过根路径的常用方法通过以下例题来呈现。


【例1】POJ 1741 Tree


题目大意:


给出N(1 <= N <= 10000)个结点的树,求使得路径u -> v长度不超过k的点对(u, v)的个数。


算法分析:


首先我们对这棵树进行点分治,接下来考虑处理以root为根的子树。

记d[x]为x到root的距离,那么我们把子树的所有结点的d拉出来,即转化为了a[x] + a[y] <= k的(x, y)对数,这是可以通过排序后扫一遍解决的。

然后,这样可能出现重复的情况(x, y在root的同一儿子内部),那么我们只需要再对root的每个儿子进行同样的操作,但是是从之前的答案中减去。

时间复杂度O(Nlog^2N)。


由于博客存不下,直接放网址:
http://hi.baidu.com/strongoier/item/fe47a4191c18a37c1009b515
主要是题目练习,以下是算法总思路(主要推荐论文)。

将无根树转化成有根树进行观察。满足条件的点对有两种情况:两个点的路径横跨树根,两个点位于同一颗子树中。

如果我们已经知道了此时所有点到根的距离a[i],a[x] + a[y] <= k的(x, y)对数就是结果,这个可以通过排序之后O(n)的复杂度求出。然后根据分治的思想,分别对所有的儿子求一遍即可,但是这会出现重复的——当前情况下两个点位于一颗子树中,那么应该将其减掉(显然这两个点是满足题意的,为什么减掉呢?因为在对子树进行求解的时候,会重新计算)。

在进行分治时,为了避免树退化成一条链而导致时间复杂度变为O(N^2),每次都找树的重心,这样,所有的子树规模就会变的很小了。时间复杂度O(Nlog^2N)。

树的重心的算法可以线性求解。


  评论这张
 
阅读(152)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018