树型动态规划 tree dp.docVIP

树型动态规划的应用 (讲稿) 树型dp是近年来才出现并迅速流行的一种新体型，到目前已经在各种oi竞赛中广泛出现，今天我们就对它做一点基本的探讨。 首先我们结合一个例子来说明什么是树型dp以及它的一些特点。 我们先来简述一下题意，题目给出了一棵圣诞树，树上的每个结点都有一盏灯，一盏灯可以打开当且仅当它的所有孩子结点上的灯是开的，最终要将根结点上的灯打开，每一种不同的开灯方案都对应着一个在任意时刻同时亮着的灯的数目的最大值，要求一种开灯方案，使得这个最大值最小。 问题描述 这是安徽省1999年省赛的题目，虽然比较古老，但是很有典型性。 如图，根结点是C，他有3个孩子，为了要打开1，我们要打开D、B、E，从直观上考虑，，我们如果计划先打开B，那么一定不会在还没有打开B之前就去进行一些对打开B没有帮助的工作，比如试图打开D，这不难证明，我们完全调整一下策略，先打开了B，再去打开D，这样至少不必原来的方案差，那么我们再来考虑如何打开B，这是我们需要处理的是以B为root的一棵树，而目标也是一样的，使得在任意时刻同时亮着的灯的数目的最大值最小，我们发现这个问题与原问题是十分类似的，实际上这就是本问题的最优子结构，它完全符合动态规划的性质，也可以dp求解，比如我们求出打开打开一个结点root的所有孩子son[1],son[2],son[3]…son[k]分别需要dp[1],dp[2],dp[3],…,dp[k],且dp数组已经按照从大到小排序，那么我们就应该按照这个顺序来开灯，既先开第一个孩子，…….，本问题得以解决。 以上的问题还可以做出一些拓展，OIBH#8练习赛的攻占巴格达一题就是由本题引申而来的，后面我们会详细讨论。 上面是例子不难，我们来归纳一下树型dp这种dp模型的一般特点。 1 题目往往是一个树的模型 2 题目往往是要求一个最优化问题 3 题目的问题具有最优子结构，可以递归求解 4 树的优美性可以保证dp的无后效性 下面我们由易到难看几个例子： Baltic Gems 题目描述 题目的意思十分简单，给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数，唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。 看到树的模型，又是一个最优化问题，我们自然想到了树型dp，但是应该怎样运用呢？ 我们来看这个最简单的例子，我们先尝试为根结点1标上一个值，假设我们标上了1，那么接下来要为以2、3、4、5为根的子树标值，因为题目中的限制条件，这些子树的根都不能再标上1，而这些子树之间彼此并不存在制约关系，所以我们可以分别递归的加以解决，dp的算法边产生了： f[root,i]=min{f[son1,i1](i1I)}+ min{f[son2,i2](21I)}+ min{f[son3,i3](i3I)}+…+ min{f[sonk,ik](k1I)} 其中f[I,j]表示在以I为根的这棵树中如果根I标上了j，最优的结果是多少。 但是随即又出现了一个问题，题目中最多会有10000个结点，就是说最多会有10000种颜色，那么我们的dp算法在时间和空间上都是无法承受的，但是实际上颜色数不会太多，这从直观上很容易理解，实战时们可以让程序的规划范围尽量大，本题中取到200就足够了，事实上经过实验，最多只要3中颜色就可以了，具体的证明我还没有想明白，欢迎大家与我讨论。 上面的这个题目状态比较明显，状态转移也不难想到，但是更多的题目需要一定的分析才能找到合适的dp方法。 Noi2003 题目描述 这是noi继2002年后连续第二年出现树型dp的题目，2002年的dragon在srbga的书上讲的非常详细了，这里着重看一下jerrygen。 首先明确一点，题目中所有的路径都是指树上两结点间的唯一路径也是最短路径，我们首先来看一下这种最长的情况可能怎样出现。 这是唯一两种路径的分布情况，对于第一中情况，我们只要求出在树上距y最远的两个点就可以了，但是第二中情况就比较复杂了，我们发现从x，y，z上很难找到突破口，不妨把目光投向这两个路径的交点o，接着我们有了惊喜的发现，ox，oy，oz一定是距离点o最远的三个点！我们只要对每个点分别求出距离它最远的三个点就可以了。 这样我们最终将问题化归为，对与树中的所有点，求出在树中到他距离最远的三个点的距离，这很明显可以dp，问题可以解决了。 最后再来看一个模型更加隐蔽的题目 Balkan [问题描述] 有一个部族有N个人，这里有一个他们的家族树，1是根节点表示父亲和儿子的关系。节点1是树