点分治算法、树链剖分算法在竞赛中的应用

算法合集之《分治算法在树的路径问题中的应用》

最近拜读了下大神的文章,仔细学了下点分治以及树链剖分,受益匪浅,对这个专题感兴趣的同学强烈推荐这篇论文。
下面我对于几道例题做一下讲解。
poj1655求树的重心

http://poj.org/problem?id=1655
首先讨论一下树的重心,重心的定义是去掉这个点之后,产生森林中树最小的点。那我们做的时候就可以一边DFS搜索就行,对于去掉某一个点来说,产生的新树要不就是它的子树,要不就是它的父亲节点向上产生的树,所以比较一下就可以AC了。

POJ1741

http://poj.org/problem?id=1741
求$$dis(i,j)\leqslant K$$的点对数量,$$n\leqslant 10000$$。
这是一个非常明显的点分治,记$$Depth(i)$$表示点i到根结点的路径长度,$$Belong[i]=x$$(X为根结点的某个儿子,且结点i在以 X 为根的子树内)。那么我们遍历所有节点,在这个点被包含的新树里面,先求出重心$$root$$,然后要统计的就是:
满足$$Depth(i)+Depth(j)\leqslant K$$且$$Belong(i)\neq Belong(i,j)$$的$$(i,j)$$个数
= 满足$$Depth(i)+Depth(j)\leqslant K$$的$$(i,j)$$个数 – 满足$$Depth(i)+Depth(j)\leqslant K$$且$$Belong(i)=Belong(i,j)$$的$$(i,j)$$个数 。

SPOJ1825

http://www.spoj.com/problems/FTOUR2/
这一次统计的是使得经过的黑点数不超过K个,且路径长度最大,$$n \leqslant 200000$$。
具体做法详见论文,我这里附上我的详细代码。

SPOJ375

http://www.spoj.com/problems/QTREE/
现在开始进入树链剖分。
这个题问的是可以修改某些边权,然后问你两个点之间的最大边权是多少。
首先我们要这一颗树线性化,这里我们要先按照重边走,没有重边就走轻边,按照遍历的顺序建立线段树,那么其实算法到这里,基本上就和分治没有关系了,专心写线段树就好了,线段树维护的就是区间最大值。
那么查询的时候,其实就是两个点慢慢往最近公共祖先移动的过程,注意,对于重边来说,不是一个一个点往上移动,而是直接跳到重链头部,这样节省时间,具体详见代码。

SPOJ2798

http://www.spoj.com/problems/QTREE3/
这个题其实比上一道题水一点,求的是距离1节点最近的黑点。那么我们建立线段树的时候,维护的就是区间的最左端点,这里需要深刻理解一下,因为有人可能认为,最左节点不一定是最浅的点呀,但是仔细想一下,我们对于一次查询,只有当$$if(segtree[i].l==l&&segtree[i].r==r)$的时候,我们才会使用这个区间存下的值,那么我们在查询的时候已经会保证l,r这段在树上的路径在线段树中是连续分布的,所以这么查询是没有问题的,一开始提交的时候一直是41.67分,后来发现1 1 这种查询并不能过,改之后100分。

最大权闭合图

昨天在做多校联赛的时候偶然碰上的,学习了下这个,首先推荐胡伯涛的《最小割模型在信息学竞赛中的应用》。
一个有向图 的闭合图(closure)$$G= (V , E)$$是该有向图的一个点集,且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。更形式化地说,闭合图是这样的一个点集$${V}’\in {V}$$ ,满足对于 $$\forall {u}\in {V}$$引出的 $$\forall \left \langle u,v \right \rangle \in E$$。那么给每个点$$v$$分配一个点权$$W_{v}$$(任意实数,可正可负)。大权闭合图(maximum weight closure),是一个点权之和大的闭合图,即大化$$\sum_{ v\in {V}’ }W_{v}$$。

那么,我们的做法就是当$$W_{v}$$是负的时候,建一条边$$\left \langle v,t \right \rangle$$容量为$$-W_{v}$$,当$$W_{v}$$是正的时候,建一条边$$\left \langle s,v \right \rangle$$容量为$$W_{v}$$,然后对于原来的边$$\left \langle {u}’,{v}’ \right \rangle$$保持不变,建一条$$\left \langle {u}’,{v}’ \right \rangle$$容量为$${inf}$$的边。那么易证这个图的在最小割的情况下,和$${s}$$相联通的子图是最大权闭合子图。
所以我们做法就是跑一次最大流,然后最大权闭合图的权值就是总收益-最大流。

POJ2987
这是一个非常裸地最大权闭合图,当$$W_{v}$$是负的时候,建一条边$$\left \langle v,t \right \rangle$$容量为$$-W_{v}$$,当$$W_{v}$$是正的时候,建一条边$$\left \langle s,v \right \rangle$$容量为$$W_{v}$$,然后对于原来的边$$\left \langle {u}’,{v}’ \right \rangle$$保持不变,建一条$$\left \langle {u}’,{v}’ \right \rangle$$容量为$${inf}$$的边。
然后直接按照原理跑一下最大流就好。

HDU4971

水题。

HDU5855
首先膜拜一下朝鲜队的出题大哥,题目质量太好了。
这道题我们直接二分最短的时间,然后对于每一次时间判断一下最大权闭合图是不是大于L就好。