一类树型动态归划问题的解法

1、一类树型动态归划问题的解法广西柳州铁路第一中学林涛【摘要】树型结构具有良好的阶段划分性质，是动态规划的一种常见模型。一般的树型动态规划都是单向的，即从叶子到根，然而近年来，出现了不少非单向的树型动态规划问题。本文以几个典型的例子为说明，介绍这类树型动态规划的解法。数据生成器（NOI2003）问题描述：在一棵有n个点的树中找三个点X，Y，Z，使他们满足：X到Y的距离不大于X到Z的距离；在满足1的情况下，使X到Y与Y到Z的距离之和最大。分析：上图是一个简单的例子，假设所有边的花费为1。通过观察发现，X到Y与Z的路径有个关键的分叉点P（如果X，Y，Z在同一路径上，那么P就是X点）。P点把X，Y，Z之

2、间的路径分成三部分，设PX花费时间a，PY花费时间b ，PZ花费时间c。根据题意有：a+ba+c，距离和为a+2b+c。假设我们知道a、b、c，但是并没有确定X、Y、Z分别是哪个点，由于我们希望距离和尽量大，在a+b+c确定时，那么就是希望b尽量大，又因为b不能是最大的，所以b是第二大的数时，距离和最大。如果P点已经确定，那么当a，b，c越大，距离和也就越大，也就是说所求的三点，应使他们在P的三个不同的分叉上（分叉不足三个用P代替），并且三点到P的距离尽可能大。显然在点P己确定的情况下，只需以P为根，对这棵树进行一次遍历即可，而一次遍历的时间复杂度为O(n)。问题是题目中点P并没有确定，但我们

3、依然可以通过枚举P，将每个点都作为根对该树进行遍历，共需n次遍历，如此可解决该题，总的算法时间复杂度为O(n2)。不幸的是n太大，必须寻找更优化的方法。题目给出的是一棵无根树，所以求P的三个最远点不好下手，我们不妨假设树的一个节点为根，那么所有点到它们儿子的三个最远点可以通过一次遍历求出来。我们观察除了根节点外的其它点，它们所得到的三个最远点仅仅是漏考虑了通向根节点的分叉，于是我们想办法把没有考虑的分叉补上。假设在上述算法中，P是Q的父亲节点，P的三个最远点已经知道是A，B，C，Q已经记录了儿子中的三个最远点。Q点还有P分叉没考虑，如果P分叉的一个点能够加入Q的三个最远点中，那么这个点一定是除

4、了Q及Q的儿子外，到达P的最远点。由于P点的三个最远点已经被求出，在这三个最远点中，最多有一个是属于Q分叉的，这个点是不能考虑的，那么哪个是属于Q点分叉的呢？由于这个属于Q分叉的最远点一定是和Q距离最远的Q的儿子，所以我们只要拿这个儿子到P的距离d与A，B，C到P的距离相比，如果能则去掉A，B，C中的一个到P的距离与d相等的点，然后我们就可以找出Q点的P分叉中，距离Q最远的点。由于算法已经求出假设的根节点的三个最远点，那么由这个根节点往下，就可以求出所有点的三个最远点。算法复杂度是O(n)。这题与一般的树型动态规划不同的是，它要考虑一个点的所有分支，而不是在给定一个根节点的情况下，只考虑它的儿

5、子。我们从一般的题目出发，假设了一个根节点，同时考虑这题的特殊性，抓住父亲节点与儿子节点的关系，把每个节点的所有分支都考虑了，很好的解决了该题。部落会议(Balkan2003)问题描述：给定了一个部落的人际关系树，树中相邻点之间有直接的亲戚关系。他们按一定的顺序到会，每个人都不愿和与他有直接关系的人坐同一排，但又想尽量靠前坐，也就是说，他会坐在最前的一排，这排没有与他存在直接关系的人坐着，求这个部落的人最多能占据多少排。下图按照2 5 3 4 1的顺序，最多能占据3排。分析：要求一共能占据多少排，那么就是要使某一个人能坐到尽量靠后的排。在解决问题之前，我们要考虑这样几个问题。假如一个人能坐到第

6、n排，那么他必然能坐到1到n排，因为他坐到第n排的时候，他的相邻点能占据1,2n-1排，那么让占据1的先坐，然后到占据2的，。只要他在适当的时候插入，就能坐到1至n排之中的任意一排。另外，如果一个人能坐到第n排，那么他的相邻点一定能分别占据1到n-1排，由于这个点之后才到会，所以之前，每个相邻点都是凭着去掉这个点后的某个子树的人际关系，坐到一个适当位置的。更确切的说，一个点能坐到第n排，按照一定顺序，他的相邻点p1、p2、p3能坐到的最后排a1、a2、a3满足a1=1,a2=2,a3=3。所以在得知一个点的所有相邻点能坐到的最大排后，坐到第一排的肯定用最小的，坐到第二排的肯定用次小的，我们按他

7、们能坐到的最大排来排序，就能很容易的判断一个点能坐到第几排。这题也是要考虑一个点的各个分叉，我们可以先假设树有一个根，我们先求一个点能凭借它的儿子坐到多少排。然后我们发现，我们没有考虑了一个点通向根的一个分叉，我们需要把漏掉的补上。假设P是Q的父亲节点，P能坐到的最大排已经求出。P要为Q服务，就必须将P的减掉Q这个分支后，再求它坐到的最大排，把P加入Q的相邻点，由于根节点已经完全考虑，我们从根节点往下，就能把所有点求出。这一题比NOI2003的数据生成器复杂，所以实现起来有以下注意的地方：在求一个点凭借儿子能坐到的最大排的时候，儿子的顺序很重要，所以要对所有点的儿子按照能坐到的最大排从小到大排

8、序，由于儿子的总数是O(n)级别的，所以复杂度是O(nlogn)。排序后，从小到大扫描儿子，从第1排开始，能坐就坐，这样就可以求出所有点当前能坐到的最大排。我们要计算P去掉一个节点Q时，还能坐到第几排时，要记录一个保险系数。在1排序后的扫描中，某个点X以前的兄弟已经能坐到第i排，而X不能坐到i+1排，只能坐到第i排，那么保险系数至少是i，因为当X的兄弟中去掉一个能坐到不大于第i排的儿子后，能用X补上。同样的，如果删去的Q能坐到第i排以上，那么不能用X补上，如果没有更大的保险系数，P能坐到的最大排就要减1。Q点在它的父亲节点P为它服务后，相当于Q多加了一个儿子，这里我们不需要想什么二叉树之类的复

9、杂方法将P插入Q的儿子中，只用最普通的循环查找，和简单的数列插入即可。因为所有的儿子总数为O(n)级别，每个点的儿子序列只会被插入一次，总的查找、插入时间也是O(n)的。当然，在插入后，要记得更新保险系数。那么本题的复杂度就是O(nlogn)。本题虽然难度加深，但是与NOI2003数据生成器的思路是一致的，就是先假设一个根，再把没考虑的考虑完全。攻占巴格达（OIBH）问题描述：在一个城区中，部队可按如下方式进行部署：1你可以占领街区i，当且仅当与i相邻的街区只有一个没有被占领2你可以控制街区i，当且仅当与i相邻的街区全部被占领（我们讲i与j相邻当且仅当存在一条街道连接i和j)3占领和控制都是需

10、要派遣一支部队，过去执行任务的, 在执行任务的部队不得执行其它任务, 除非要放弃当前所占领或控制的街区4不可以控制曾经被占领过的街区你的目标是调遣尽可能少的部队控制一个街区(注意: 只需要控制一个街区,不需要把所有街区占领)。提示：你可以调遣正在执行占领任务的部队，但其所占领的街区将失去占领状态。分析：显然，如果一子图中有环，由于环上的点互相牵制，不可能占领，那么子图中任何一个街区不可能被控制。所以我们只用考虑树状的子图，为了使问题更简化，我们就单独考虑一棵树。我们先观察树上的一个点，它要被控制，只能占领它周围的所有点，也就是要考虑它的各个分叉。我们不妨按照前面的两题，先假设一个节点为根，那么

11、我们可以求出一个点凭借它的所有儿子被占领而将其控制所需要的部队数。占领的部队数不是简单的叠加，假设一个点的儿子被占领分别需要a1,a2,a3,a4an支部队。那么当用去a1支部队时，我们只要保留占领这个儿子的一支部队，而其他a1-1支部队都能用于别的儿子的占领，那么占领所有儿子需要的部队为maxai+i-1。我们马上发现，数列ai在递减排列时，能使总部队数最小。其实这个道理很简单，由于需要最大部队数的儿子，早晚要用去a支部队，不如先占领它，而空余比较多的部队去占领其他儿子。按照上述的算法求解之后，除根节点，每个节点都没有考虑其通向根节点的分叉。我们将漏考虑的条件补上，考虑P已经求出控制它需要的

12、部队数，而Q是P的一个儿子节点，我们注意以下几个地方：我们要把每个点的儿子按照占领所需部队从大到小排序，注意节点本身算一个需要一支部队占领的儿子。排序之后就可以求出占领每个节点需要的部队数，按上述方法，部队数为maxai+i-1。删除保险系数，顾名思义，就是一个节点X删去一个要被占领的相邻点Y时，占领X的部队所需要的部队会如何变化。为了方便求解，我们在上述算法中同时记录一个ai+i-1的第二大值（第二大值可以和最大值重复），假如Y是X的相邻点中需要占领部队数（设为a）最多的，而且a就是ai+i-1中的最大值，那么删除Y，所有的儿子往前移动，新的最大值为第二大值减1。对于其它情况，那么我们在1的求解最大值过程中，记录最大值出现的最前位置比如为ai，那么如果a=ai，出现最大值的儿子往前移动，最大值要减1，否则不变。将Q的P分叉加入对Q的限制，还是可以采用最简单的循环查找，最简单的直接插入，复杂度为O(n)，理由同上一题。至此，该问题就被解决了，算法中分割子图、判断子图是否是树的复杂度略去，那么该题的复杂度为O(nlogn)。总结在做完这三题后，我们发现虽然三题难易不同，但都采用的是同一个思路：问题要考虑树中一个节点的各个分叉，我们先假设一个根节点，考虑每个节点的儿子分叉。现在除了