nbhkdz.com冰点文库

2014信息学奥林匹克夏令营-day4树形DP(洪鑫焰)


常州市第一中学 洪鑫焰

引言
? 树形结构是信息学奥赛中重要的数据结构模

型之一,有关树形结构的试题在竞赛中也经 常出现。鉴于在树形结构上使用动态规划算 法已成为近年来信息学奥赛的考察热点,本 文将重点围绕动态规划算法在树形结构上的 应用进行阐述。首先对树形结构的特点和动 态规划的应用条件进行简要介绍,然后对动 态规划在树形

结构上的各种应用进行举例说 明,最后进行总结,并提供了几个实战题目。

树形结构的主要特点
?

1、在一棵树里,除了根节点以外的所有 节点有且只有一个父亲节点,根节点没有 父亲节点。除了叶子节点外,所有的节点 有一个或多个孩子节点,叶子节点没有孩 子节点。

?

2、一棵树里任意两个节点之间都有且只 有一条通路,如果把任意一节点与其相邻 节点之间的通路看作一条无向边的话,那 么一棵树里没有环及重边的存在。因此, 一棵有N个节点的树恰好有N-1条边。

?

3、树是具有递归结构的。一个节点即是 一棵树,而一棵有孩子节点的树,若其根 节点为a节点,则其任意一个孩子节点b, 与所有不用通过a节点即可和b相连的节点 也构成一棵树,称为以b为根的a的一棵子 树。b的任意一棵子树也是a的一棵子树。

?

4、树是具有层次性的。如果一棵树是有 根的,那么某个节点a的深度 d(a)=d(father(a))+1,其中father(a)为 a的父亲节点。特别的,d(root)=1。

?

5、对于一棵树进行深度(或宽度)优先遍 历后,每个节点的孩子节点的时间戳都是 大于该节点的。

树的遍历
?

对一棵树的遍历一般有两种途径。第一种 是深度优先遍历,第二种是宽度优先遍历, 这两种遍历方法对一棵树进行遍历后,会 得到不同的遍历顺序。在一般的使用中, 这两种遍历都是十分重要的。

? ? ? ? ? ? ? ?

以深度优先遍历为例,我们可以写出如下伪代 码: void dfs(x){ x的时间戳=++time; 对于x的每个孩子y, dfs(y) } 这种深度优先遍历的时间复杂度是O(N),N为树 中的节点数。

动态规划算法必须满足的条件
?

1、阶段性。整个问题的求解可以划分为 若干个阶段的一系列决策过程(与树的层 次性相对应)。

?

2、最优子结构性质。一个最优化策略具 有这样的性质,不论过去状态和决策如何, 对前面的决策所形成的状态而言,余下的 诸决策必须构成最优策略。简而言之,一 个最优化策略的子策略总是最优的(与树 的递归结构相对应)。

?

3、无后效性。将各阶段按照一定的次序 排列好之后,对于某个给定的阶段状态, 它以前各阶段的状态无法直接影响它未来 的决策,换句话说,每个状态都是过去历 史的一个完整总结(与dfs的时间戳特点 相对应)。

例1
? ? ?

周年庆宴 Hdu 1520 Anniversary party 【题目描述】 Ural大学有N个职员,编号为1~N。他们有从属关系,也就是说他们 的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。每个职 员有一个快乐指数。现在有个周年庆宴会,要求与会职员的快乐指数之和 最大。但是,没有职员愿和直接上司一起与会。 【输入格式:】 第一行一个整数N。(1<=N<=6000) 接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。 最后一行0 0表示结束。 【输出格式】 输出最大的快乐指数和。

? ? ? ? ?

? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【 样例输入】 7 1 1 1 1 1 1 1 13 23 64 74 45 35 00

【样例输出】 5

简化
?

如果关系构成一条链?

重标号后,i能不能参加舞会只和i-1有没 有参加舞会有关。 ? 所以用
? f[i][0] 表示i不参加舞会的情况下,前i个人 能达到的最大快乐指数和。 ? f[i][1] 表示i参加舞会的情况下,前i个人能 达到的最大快乐指数和。
?

?

考虑转移
? 如果i参加,i-1就一定不能参加 ? 如果i不参加,i-1可以参加也可以不参加

?

很容易写出如下转移
? f[i][0]=max{f[i-1][0],f[i-1][1]} ? f[i][1]=f[i-1][0]+R[i]

?

再考虑一般的树形情况。
? i能不能参加舞会只和i的孩子有没有参加舞

会有关,和以i的孩子为根的子树如何决策无 关。
?

所以用:
? f[i][0]

表示i不参加舞会的情况下,以i 为根的子树能达到的最大快乐指数和。 ? f[i][1] 表示i参加舞会的情况下,以i为 根的子树能达到的最大快乐指数和。

?

如何转移?
? 如果i参加,i的孩子就一定都不能参加 ? 如果i不参加,i的孩子可以参加也可以不参


?

因此:
? f[i][0]=∑max{f[j][0],f[j][1]} ? f[i][1]=∑f[j][0]+R[i] ? 其中j为i的孩子

?

参考代码 HDU_1520.cpp

例2
? ? ?

电脑网络(Hdu 2196 Computer) 【问题描述】 一所学校在几年前购进了第一台电脑(这台电脑的编号为1)。 最近几年,学校又购买了N-1台电脑,每台新电脑和之前的某一台电脑 连接。学校的管理员想知道对于每一台电脑i,到与它距离最远的电脑 的距离Si。你需要提供这个信息。

Hint: 样例输入如图所示,从图中你 可以知道,4号电脑到1号电脑的距离 最远,所以S1=3。4号电脑和5号电脑 到2号电脑的距离最远,所以S2=2。5 号电脑到3号电脑距离最远,所以S3=3。 由此类推S4=4,S5=4。

? ? ? ? ?

【输入格式】 输入文件包含多组测试数据,对于每组测试数据: 第一行包含一个整数N (N<=10000) ; 接下来N-1行描述每一台电脑。第i行包含两个用空格隔开 的整数y、l,表示i号电脑与之前的y号电脑连接,距离为l。 所有l之和不超过10^9。 【输出格式】 对于每组测试数据输出N行,第i行表示离i号电脑的最远 距离Si。

? ?

? ? ? ? ? ? ? ? ? ? ? ? ?

样例输入: 5 1 1 2 1 3 1 1 1 样例输出: 3 2 3 4 4

问题分析:
由于题目告诉我们“每台新电脑和之前的 某一台电脑连接”,这与每个非根节点只有 一个父亲对应,所以得出: ? 所有电脑与之间的连接构成了一棵树。
? ?

问题就转化成了,给定一棵有边权的树, 求第i台电脑与距离它最远的电脑之间的距离 Si。

?

最暴力的方法:
? 对于每台电脑,以它为起点,进行一遍BFS或

DFS,找距离它最远的电脑。 ? 时间复杂度O(n^2)。
?

有没有更快的做法?

?

我们在做DFS的时候可以做一些改进:
? 当我们确定一个点为起点的时候,这棵树就

? ? ? ?

成了一颗有根树,我们不妨记录以每个点i为 根的子树中,距离该点的最长路f[i], f[i]=max(f[j]+len[i][j]),其中j为i的孩 子。 那么,我们同样能在O(n)的复杂度内得到根 的答案f[root]。 这样做,我们还是需要枚举每个点作为根。 复杂度还是不变!

反思
? ?

但是我们忽略了: 改进后,我们在第一遍DFS后就得到了以每个点为根 的子树中到该点的最长路,我们只差该点经过它父 亲得到的最长路,离要求的答案仅有一步之遥!

显然,f[root]即为root的答案,我们接下 来考虑root的孩子i,有人认为i的答案就是 max(f[i],f[root]+len[root][i])。 ? 这是不对的,因为有可能f[root]是root经 过i得到的,这样我们以i为起点的时候 f[root]+len[root][i]相当于走了i->root>i这样的非法路径。
?

如何才能解决这个问题呢?
?

? ? ? ? ?

我们只要在第一遍DFS的时候记录下每个点i为 根的子树中,距离i的最长路、次长路分别为 f[i][0]、f[i][1](保证最长路和次长路经过i 的两个不同的孩子)并记录对应的经过的孩子 g[i][0]、g[i][1]。这样我们在考虑root的孩 子i时, 如果g[root][0]!=i,i的答案就是 max(f[i],f[root][0]+len[root][i]); 否则,i的答案就是 max(f[i],f[root][1]+len[root][i]), 同时更新f[i]和g[i],以便计算i的孩子的答案。

?

可以发现我们在计算一个点i的答案时, 必须要先知道它的父亲的答案。只要用 DFS的顺序计算就可以了。 两遍DFS,每次转移都是O(1),总复杂度 O(n)。 参考代码: HDU_2196.cpp

?

?

例3
? ? ? ?

黑手党(Poj 3107 Godfather) 【问题描述】 去年的芝加哥充满了黑帮争斗和奇怪的谋杀。警察局长真的 厌倦了所有这些罪行,决定逮捕黑手党领袖。 不幸的是,芝加哥黑手党相当复杂的结构。没有人知道黑手 党的信息。警方已经追踪他们一段时间的活动,并且知道他们中 的一些人互相通信。根据收集到的资料,警察局长表明黑手党的 层次结构可以表示为一棵树。黑手党首脑是树的根,每个节点表 示一个人,一个节点的孩子即为这个节点表示的人的直接下属。 更不幸的是,虽然警方知道了匪徒的通讯,他们不知道谁是 黑手党首脑。因此他们只有通信关系的无向树。 基于这样的思想,警察局长猜测可能表示黑手党首脑的节点 必须满足:在删除它后,包含最多节点的剩余连通块的节点数最 小。帮助警察找到所有可能成为黑手党首脑的节点。

? ?

?

? ? ? ? ? ? ? ? ? ? ? ? ?

【输入格式】 第一行包含一个整数n(2≤n≤50000),表示有n个人,编号为 1~n。 接下来n-1行,每行两个数x,y,表示编号为x的人和编号为y 的人之间有通信。 【输出格式】 输出所有可能成为黑手党首脑的人的编号,按升序排列,两个 编号之间用空格隔开。 【输入样例】 612 23 25 34 36 【输出样例】 23

简化题意
? 给定一棵树,将树上的一个节点删除后会得

到多个连通块,求删去哪些点后,所得到的 连通块的节点的最大值最小。

?

最暴力的方法:
? 枚举删去节点i,对剩余节点,进行一遍BFS

或DFS,找到每个联通块,计算其节点数大小, 最大值记为f[i],用f[i]去更新答案,求出 最小值ans。将f[i]==ans的i按照升序输出即 可。 ? 时间复杂度O(n^2)。

更快的做法
我们可以仿照上一道题的做法,在 做DFS的时候记录以每个点i为根的子树中, i删除后的最大连通块的节点数f[i] ? f[i]=max(size[j]),其中j为i的孩 子,size[j]为以j为根的子树的节点数。 ? 那么,我们同样能在O(n)的复杂度 内得到根的答案f[root]。
? ?

如何求其它点的答案呢?

? ?

还需要记录最大值和次大值吗?

其实不用了,因为我们发现如果将i删 去,那么i的父亲所在的联通块的节点数 就是n-size[i]。 ? 所以,我们进行一遍DFS就能求出所有 点的答案。
?

参考代码:POJ_3107.cpp

例4
? ? ?

电视网络(Poj 1155 TELE) 【问题描述】 电视网络计划广播一个重要的足球比赛。他们的网络传输关系可以 认为是一棵树。树的根即为广播比赛的电视台,叶子节点表示网络用 户,其他节点表示中转站。 从一个节点向另一个节点传输广播的费用是给定的。总的传输费用 为所有传输广播的边的费用之和。 每个用户愿意支付一定的报酬来观看足球比赛,电视网络决定是否 给其提供广播信号。 写一个程序计算在电视网络不亏本的前提下(即看到比赛的用户的 报酬之和-总的传输费用>=0),最多可以让多少人看到足球比赛。

? ? ? ?

? ? ? ? ?

? ? ? ?

【输入格式】 第一行包含两个整数N,M(2<=N<=3000,1<=M<=N-1)分别表示 总的节点数和叶子节点数。 根节点的编号为1,叶子节点的编号为N-M+1~N,其他节点的编号 为2~N-M。 接下来N-M行,每行按照如下格式输入:K A1 C1 A2 C2……AK CK 表示一个非叶子节点(中转站或电视台)能向K个节点(中转站或用 户)传输广播,每一个数对A,C分别表示接收的节点编号和传输的费 用。 最后一行包含M个整数表示每个人愿意支付的报酬。 【输出格式】 一行一个整数,表示在电视网络不亏本的前提下最多可以让多少人 看到足球比赛。

? ? ? ? ? ? ? ?

【输入样例】 96 3223293 24252 3627282 433311 【输出样例】 5

化简题意
? 给定一棵带边权的有根树,叶子节点有收益,

求最多能选多少叶子节点,使得其收益之和 不小于从root到这些叶子所需要经过的边的 权值和(每条边的权值只算一遍)。

?

不知道从何下手? 这是树形DP专题!

?

DP的三大要素
1、状态表示、 ? 2、转移方程、 ? 3、特殊边界。
?

?

这在树形DP上同样适用!

?

用动态规划算法解题首先要做的是确定好 状态,这应该是不容置疑的,因为状态表 示是动态规划中的重中之重。一般地,树 型动态规划的状态中会有一个参数i,表 示此状态的研究对象是以i为根的子树。

如何设计状态?
?

一个想法: ? 用f[i]表示以i为根的子树,在不亏本的前提下, 最多能选多少个叶子节点。

如何转移? ? 考虑转移的时候我们发现,对于子树i来说,并 不能通过它的孩子j得到的f[j],来得到f[i],因为: ? 第一:f[j]只保证在j为根的时候不亏本,并不 能保证在i为根的时候也不亏本。 ? 第二:其实并不需要限制所有的孩子j都不亏本, 一个孩子暂时亏本,但是加上另一个孩子的收益就 不亏本了。
?

?

所以,我们的状态表示有问题,我们需要容忍暂时的 亏本,还需要知道在某状态下的实际收益。 这时候,一维的状态已经无法满足了。

?

于是,我们用 ? f[i][j] 表示以i为根的子树中,选取了j个叶子节 点,最大的收益是多少。
?

?

如何转移? 对于f[i][j],我们需要将j分给i的若干 孩子,难道还需要枚举j拆分? 怎么办?

?

?

提示
?

回忆一下背包的过程。 这不就是背包吗! 把j当成背包体积,f[i][j]为该体积下的价 值。对于i的每个孩子k只能从若干体积中选 一个,所以这是一个典型的分组背包的模型。

?

?

很容易写出转移方程: ? f[i][j]=max{f[i][j],f[i][jp]+f[k][p]} ? 边界就是对于所有叶子节点s, f[s][1]=pay[s]。其中,pay[s]为s愿意支付 的报酬。
? ?

最后,满足f[1][j]>=0的最大的j就是答案。

? ? ? ? ? ? ? ?

复杂度? O(sigma(sum[i]^2)) 其中sum[i]表示i为根的子树中的叶子节点数。 其实,是可以构造数据,使得实际复杂度为n^3的。 怎么办? 启发式合并! dp时可以按照孩子的sum值从大到小做,可以证明复 杂度为O(n^2logn)。 参考代码:POJ_1155.cpp

例5
?

消防站(Poj 2152 Fire) 【问题描述】 Z国有N个城市,编号为1~N。城市之间用高速公路连接,任意两 个城市之间有且仅有一条路径。 最近,Z国火灾频发,于是政府决定在一些城市建立一些消防站, 在城市K建立消防站需要花费W(K),每个城市的W可能不同。如果 不在城市K建立消防站,那么需要保证离K最近的消防站与K的距离不 超过D(K)。每个城市的D可能不同。 为了节省开支,政府希望你计算满足要求的最小花费。

? ? ?

? ?

? ? ? ? ? ? ? ? ? ?

【输入格式】 第一行一个整数T,表示测试数据组数。 接下来一共T部分,每部分格式如下: 第一行包含一个整数N(1≤n≤1000)。 第二行包含N个整数,第i个整数表示W(i)(0 < W(i) <= 10000)。 第三行包含N个整数,第i个整数表示D(i)(0 <= D(i) <= 10000)。 接下来n-1行,每行三个数u,v,L(1 <= u, v <= N,0 < L <= 1000), 表示城市u和城市v之间有一条长度为l的高速公路。 【输出格式】 每组测试数据输出一个整数,表示最小费用。

? ? ? ? ? ? ? ? ?

【输入样例】 1 5 11111 21112 121 231 341 451 【输出样例】 1

? ?

分析
受到上一题的启发,我们需要先设计状态。 ? 和上一道题相似,如果仅用f[i]表示在以i为 根的子树中,修建符合要求(子树中的所有结 点到最近消防站的距离不超过其对应的函数D 值)的消防站的最小费用——即状态只用上述 的一个参数,那么状态转移方程是无法找到的。 ? 因为这种状态表示无法反映出在哪里修建了消 防站、离i最近的消防站的详细情况。
?

为了解决这种情况,我们还是需要增加一 个参数,或者说增加一维。 ? 这时应该增加的参数应该是什么呢?
?
? i到最近消防站的距离? ? 离i的最近消防站的编号? ? 树内离i最近的消防站的编号? ? 树外离i最近的消防站的编号?

?

到底加哪个参数是可行的呢?

可是事与愿违! ? 所有的这些状态表示都难以找到好的转移 方程。 ? 难道状态还要增加一个参数吗? ? 还是这题本身是NP完全性问题、而不是用 动态规划题目?别急,先来做个分析吧。
?

现在面对的主要障碍无疑是,“每个城市在 不超过距离D(这个城市)的前提下,必须 选择最近的消防站作为负责站”这一严格限 制在状态转移中起着干扰作用。 ? 其实,我们并不须要知道最近的消防站是哪 个,而只要保证在距离D(这个城市)内至 少有一个消防站就足够了。 ? 于是可以尝试放宽这个限制:把这个限制转 化为“每个城市在不超过距离D(这个城市) 的前提下,可以选择任意一个消防站作为负 责站”。
?

?

转化后,求出的最优解与转化前的是一样 的! 原因在于在转化后,必定存在一个最优解满 足性质“每个城市在不超过距离D(这个城市) 的前提下,必须选择最近的消防站作为负责 站”。

?

?

现在每个城市都享有一定的“自由权”了, 可以在自己的活动范围内自由地选择消防 站作为负责站。 现在该如何设计状态呢?

?

? ? ? ?

? ?

令f[i][j]表示: 1、在以i为根的子树里修建一些消防站; 2、在结点j必须修建一个消防站; 3、以i为根的子树内的每个结点在不超过距 离D(这个结点)的前提下,选择一个在子 树内或结点j上的消防站作为负责站; 4、结点i必须选择结点j上的消防站作为负 责站; 的最小总费用(如果j在树外,则该负责站 的费用不算在f[i][j]内)。

为了转移方便,先定义一个简单的辅助状 态Best。 ? Best[i]表示在以i为根的子树中,修建合 符要求(子树中所有结点到其树内的负责 站的距离不超过其对应的函数D值)的消防 站的最小费用。 ? 明显地: ? Best[i]=min{f[i][j] | j在以i为根 的子树中}
?

下面对F进行分析: ? 1、当dis(i,j)>D(i)时,f[i][j]=+∞,这表示不存在状 态f[i][j];
? ?

2、当dis(i,j)<=D(i)时, ? 1)当j在以i为根的子树外时,对于i的每个儿子k都有 两种选择:选择以 k为根的子树内或外的消防站为负责 站。 ? 当选择以k为根的子树内的消防站为负责站时, 其子树所需的最少费用为Best[k]。 ? 当选择以k为根的子树外的消防站为负责站时, 易知k只可以选择j上的消防站作为负责站,此时其子树 所需的最少费用为f[k][j]。 ? 综上得到: ? f[i][j]=sigma{min(Best[k],f[k][j])} k

? 2)当i=j时,i的每个儿子的选择情况与1)中一样。此

时还要加上修j上的消防站的费用。因此: ? f[i][j]=w(j)+sigma{min(Best[k],f[k][j])} k为i的孩子
? 3)当i!=j并且j在以i为根的子树内时,此时j必定在i

的某个儿子child的子树。 ? 对于i的每个不是child的孩子其选择情况与1中 的一样。 ? 而对于child,它只能选择j作为负责站。 ? 综上得到:
?

f[i][j]=f[child][j]+sigma{min(Best[k],f[k][j])} 其中,k为i的孩子且k!=child

复杂度分析: ? 时间复杂度为O(n^2) ? 空间复杂度为O(n^2)。
? ?

参考代码 POJ_2152.cpp

总结
本文的主要内容是动态规划算法在树形结 构上的使用,通过以上几道例题的详细分析,我 们对如何在树形结构上使用动态规划算法也有了 一定的了解。 ? 通过以上学习,相信大家不仅对二维状态 的动态规划在树形结构上的使用有了了解,而且 通过以上介绍的思维方法,相信大家也对多维状 态的动态规划在树形结构上的使用能自行掌握。 ? 本文不仅希望通过动态规划在树形结构上 的使用的介绍让大家理解、掌握这种方法,更希 望大家能够学到更多更好的思维方法和学习方法。
?

课后练习
1、Poj 3140 Contestants Division ? 2、Poj 1947 Rebuilding Roads ? 3、Hdu 1561 The more, The Better
?

参考资料
1、DP在树型结构上的应用——欧阳云 ? 2、一张一弛,解题之道,“约制、放宽”方法在解 题中的应用——陈启峰
?