（点）分治学习笔记

哗我看了一下好像没有很详细专门讲分治的blog？那就主要先学一下点分治吧，其他的……等我记得把C++一本通带到机房来再说吧先咕着啦

写在前面

刷题进度

入门题（0/3）

好题(0/9)

问题解决进度

Q1

Q2

---

 正文

淀粉质

点分治

点分治就是在一棵树上，对具有某些限定条件的途径静态地进行统计的算法。

——《算法竞赛 进阶指南》（李煜东）

这句话看起来很高深的样子……(这本书上的话都很高深)

让我们来结合题目理解一下↓

【例】Tree  (POJ1741)

题目大意

给定一棵有n个结点的树，每条边都有一个权值。树上两个结点x与y之间的路径长度就是路径上各条边的权值之和。求长度不超过k的路径有多少条。

解题思路

本题树中的边是无向的，即这棵树是一个由n个结点，n-1条边构成的无向连通图，即这是一棵无根树。

若指定结点p为根，则对于p来说，树上的路径可以分为两类：

1.经过根结点p

2.包含于p的某一棵子树中（不经过根结点）

根据分治的思想，对于第2类路径，显然可以把p的每棵子树作为子问题，递归处理

然而……对于第1类路径，可以从根结点p分成"x～p"与“p～y”两段（——话说这不是和LCA有点联系？？），于是从p出发对整棵树DFS，求出d[i]表示i结点到根结点p的距离，b[i]表示i属于根结点p的哪一棵子树(注意b[p]=p)

此时满足题目要求的第1类路径就是满足以下两个条件的点对(x,y)的个数

——这句话特别奇怪（我感jio）……我的理解就是

如果点对(x,y)满足以下两个条件，那么x到y的路径就是上面提到的第1类路径且路径长度满足题目不超过k的要求

条件如下：

1.b[x]≠b[y]

2.d[x]+d[y]≤k

那么接下来问题来了——如何统计上述点对的个数呢？

定义函数Calc(p)表示在以p为根的树中统计上述点对(x,y)的个数

有两种实现方法：

1.树上直接统计

2.指针扫描数组

接下来分别介绍一下这两种方法QWQ

一、树上直接统计

设p的子树为s₁,s₂,s₃……s_m

对于s_i中的每个结点x，把在子树s₁,s₂,s₃……s_i-1中的满足d[x]+d[y]≤k的结点y的个数直接累加到答案中即可

具体来说，可以建立一个树状数组，依次处理每棵子树s_i

对s_i中的每个结点x，操作如下：

1.查询前缀和ask(k-d[x])，即为所求的y结点的个数

2.执行add(d[x],1)，表示与p距离为d[x]的结点增加了一个

我感jio不太明白这里要怎么实现啊……书上又没有代码，我还是去问一下dalao吧QAQ

go back

继续……

按子树一棵棵处理保证了b[x]≠b[y]，查询前缀和保证了d[x]+d[y]≤k

注意

树状数组的范围与路径长度有关，这个范围远比n要大，本题不易进行离散化

一种解决方案是用平衡树代替树状数组，以保证O(nlogn)的复杂度，但这样代码复杂度会显著增加

(真的是“显著”增加呀，因为我根本就不会平衡树QAQ，离散化也不太清楚天哪我简直是个渣渣QAQ)

两种方法各有千秋，对于这道例题来说，第二种方法更加合适，所以我接下来要讲一讲第二种方法

二、指针扫描数组

先把树中的每一个结点放进一个数组a，并按照结点距离根结点的距离(即d的值)排序

使用两个指针L，R分别从前、后开始扫描a数组

容易发现一个规律：

在指针L从左向右扫描的过程中，恰好使得d[a[L]]+d[a[R]]≤k的指针R的范围是从右向左单调递减的

另外，用数组cnt[s]维护在L+1与R之间满足b[a[i]]=s的位置i的个数

于是，当路径的一段x=a[L]时，满足题目要求的路径另一端y的个数就是R-L-cnt[b[a[L]]]

然后就……结束了？QAQ我也不懂怎么实现啊救命啊啊啊啊啊

go back

整理一下整个点分治算法的过程

1.任选一个根结点p（下面有说选根结点时的具体要求）

2.从p出发执行一次DFS，求出d数组和b数组

3.执行Calc(p)函数

4.删除根结点p，对p的每棵子树(同样看做是无根树)递归执行1~4步直至叶子结点(结束)

时间复杂度

在点分治过程中，每一层的所有递归过程合计对每个结点处理1次

因此，若递归到第T层，则整个算法的时间复杂度就是O(Tnlogn)

如果问题中的树是一条链，最坏情况下每次都以链的一端为根，那么点分治将需要递归n层，时间复杂度退化到O(n²logn)

为了避免这种情况，我们每次选择树的重心作为根结点p

此时易证p的每棵子树大小不会超过整棵数大小的一半，点分治至多就递归logn层，所以整个算法的时间复杂度为O(nlong²n)

常见问题

点分治主要可以解决的问题就是处理路径统计还有处理换根统计问题

要刷的题目

入门题  (go back)

LuoguP3806

LouguP4178

CF116D

好题(我觉得我一辈子都做不完这些题的）

树上的点对

开店

捉迷藏

qtree5

重建计划

Race

快递员

树的难题

树上游戏

 

关于重心

树的重心是什么？(有种小学作文开头的赶脚)

如果把一个结点x从树中删除，那么原来的树就分成了若干个连通块，而max表示这些连通块中最大的那个连通块的大小

若用max[x]记录删除结点x后产生的最大连通块的大小

那么整个max数组中若max[p]最小，则称结点p为这棵树的重心

go back