不撞南墙不回头——树规总结

焦作一中信息学oy

之所以这样命名树规，是因为树规的这一特殊性：没有环，dfs是不会重复，而且具有明显而又严格的层数关系。利用这一特性，我们可以很清晰地根据题目写出一个在树（型结构）上的记忆化搜索的程序。而深搜的特点，就是“不撞南墙不回头”。这一点在之后的文章中会详细的介绍。 首先是扫盲，介绍几条名词的专业解释以显示我的高端（大部分人可以略过，因为学习到树规的人一下应该都懂??）：

动态规划：

问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。动态规划就是解决多阶段决策最优化问题的一种思想方法。

阶段：

将所给问题的过程，按时间或空间（树归中是空间，即层数）特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。

状态：

各阶段开始时的客观条件叫做状态。

决策：

当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。 （即孩子节点和父亲节点的关系）

策略：

由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。

状态转移方程：

前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段（在树中是孩子节点和父亲节点）状态的演变规律，称为状态转移方程。

目标函数与最优化概念：

目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。

树的特点与性质：

1、 有n个点，n-1条边的无向图，任意两顶点间可达 2、 无向图中任意两个点间有且只有一条路

3、 一个点至多有一个前趋，但可以有多个后继

4、 无向图中没有环；

废话说完了，下面是正文： 拿到一道树规题，我们有以下3个步骤需要执行：

1. 判断是否是一道树规题：即判断数据结构是否是一棵树，然后是否符合动态规划的

要求。如果是，那么执行以下步骤，如果不是，那么换台。

2. 建树：通过数据量和题目要求，选择合适的树的存储方式。如果节点数小于5000，

那么我们可以用邻接矩阵存储，如果更大可以用邻接表来存储(注意边要开到2*n，因为是双向的。这是血与泪的教训)。如果是二叉树或者是需要多叉转二叉，那么我们可以用两个一维数组brother[]，child[]来存储（这一点下面会仔细数的）。

3. 写出树规方程：通过观察孩子和父亲之间的关系建立方程。我们通常认为，树规的

写法有两种：

a.根到叶子: 不过这种动态规划在实际的问题中运用的不多。本文只有最后一题提到。

b.叶子到根: 既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多。

注意：这两种写法一般情况下是不能相互转化的。但是有时可以同时使用具体往后看。

以下即将分析的题目的目录及题目特点：

1、加分二叉树：区间动规+树的遍历； 2、二叉苹果树：二叉树上的动规； 3、最大利润：多叉树上的动规； 4、选课：多叉树转二叉； 5、选课（输出方案）：多叉转二叉+记录路径； 6、软件安装：判断环+缩点+多叉转二叉； 【4、5、6属于依赖问题的变形】

7、游荡的奶牛：三遍bfs（先从根向叶记录拓扑序，再从叶向根传值，最后再从根向叶传值）。

所有题目的参考代码由于篇幅限制不给出了，如果需要请参考：http://www.cnblogs.com/gq-ouyang/

欢迎指正。

基本的知识掌握和步骤了，我们就通过习题来感受一下树规的魅力，先来看这样一道题：

1、加分二叉树

【问题描述】

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数

若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；

（1）tree的最高加分 （2）tree的前序遍历

【输入格式】

第1行：一个整数n（n＜30），为节点个数。

第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

【输出格式】

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。

第2行：n个用空格隔开的整数，为该树的前序遍历。

【算法&思路】：

看到这个问题，我们首先应该想到的是这道题是否属于动态规划，而这里我们发现，结合问题，如果整棵树的权值最大，必然有左子树的权值最大，右子树的权值也最大，符合最优性原理。所以是动态规划。而却不是一道树规的题目。因为我们可以用区间动规的模型解决掉：直接定义一个f[i][j]表示从i到j的最大值，则f[i][j]=max(f[i][k-1]*f[k+1][j]+a[k]),枚举k即可。接下来是如何建树的问题，只有把树建好了，才能输出其前序遍历。于是，我们看到了两个关键词：二叉树，中序遍历。有了这两个关键词，加上区间动规，这棵树就能建起来了。根据二叉树的特性来建树（这里不再具体讨论树的详细的构造了，中序遍历和前序遍历不懂得自己百度）。所以这颗树的前序遍历，只需要边动规边记录下root[i][j]=k表示i到j的根为k即可确定树的构造。

【小结】：拿到一道题目，首先我们要做的是看清题目，判断这是一道考察什么算法的题目。只有建立在正确思路基础下的算法，才是有意义的，正确的算法，也是事半功倍的算法。而此题是批着 树形 外观的 非树形动态规划题。而真正的树形动态规划是在树上做动态规划。

真正的树规来了。

2、二叉苹果树

【题目描述】：

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

【输入格式】：

第1行2个数，N和Q(1<=Q<= N,1

N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。 每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过30000个。