《国家集训队论文集栗师》-公开·课件.pptVIP

树的乐园 讲题目的 重点针对树中的动态规划讲题。体会动态规划在树这个特殊的模型下的思想。同时，也涉及到了一些其他的算法。由于树的优美性，使得各式各样的算法都有了发挥的余地。 题目1 给定一棵有n个节点的有根树，节点从1到n标号，不同的点标号不同。对于每一个节点，求在它的子孙节点中，有多少个节点的标号比它的标号小。 问题2 给定一个有n个节点的树，节点从1到n标了号。现在，给每一个点一个w值，w值的范围是1到m，并且满足，如果两个节点i,j具有相同的w值，那么，在从i节点到j节点的唯一一条最短路径上，所有节点(除了i,j)的w值都大于i的w值(也就是j的w值)。现在，要给出一个方案，使得这个方案的w值最小。 问题3 某国有n个城市，这n个城市之间有n-1条高速公路，每一条高速公路连接两个城市，并且通过这些高速公路，任意两个城市都可以互相到达。现在，消防部队要在这个国家建立若干个消防站，一个消防站建立在某一个城市中。如果某个城市发生火灾，那么距离这个城市最劲的消防站将会调动消防部队到火灾城市，假设每一条高速公路都需要花费一单位的时间。为了安全，消防部队必须在M时间内到达火灾城市，请问，至少需要建立多少个消防站？ 问题4 把上面的题目扩展一下： 1、如果走完每一条高速公路需要花费的时间不同，需要最少的消防站是多少？ 2、在1的基础上，如果每一个城市建立一个消防站都有一些费用，那么，最少需要用多少费用才能保证安全？ 问题5 给定一棵有n个节点的树，以及定义在边上的权值w，选出一个最多有p个节点的集合S。定义d[i]=min{dis[i,j],j是S中的节点}，要求这样的S，使得给定d[1]+d[2]+……+d[n]最小。 问题6 给定一棵树，以及定义在树上的边的长度，现在，要询问有多少对节点的距离小于等于K。 问题7 给定一棵树。现在，两个人轮流操作这棵树，他们的操作是：从这棵树中删除一条边，这样，树就分成了两个部分，把不包含节点1的部分扔掉，只保留含有节点1的部分。最后，谁不能这样操作了就算输了。显然，不能操作了就是指只剩下节点1了。 动态规划思想 在树中，我们不难得到树中动态规划的基本思路：一般情况下，把树看成有根树，从下到上，以每一棵子树为阶段。考虑在整个树所形成的一个“方案”中，每一棵子树有哪些状态。把这些状态用函数表示出来，找到状态与状态之间的转移关系。 * * ——一些与树有关的题目 栗师 *