Dynamic Programming on Trees 树型动态规划

https://blog.csdn.net/dcx2001/article/details/78269908
      一般来说树形dp在设状态转移方程时都可以用f[i][]表示i这颗子树怎么怎么样的最优解，实现时一般都是用子树更新父亲（即从下向上更新），那么首先应该考虑的是一个一个子树的更新父亲还是把所有子树都算完了在更新父亲？这就要因题而异了，一般来说有两种情况：1.需要把所有子树的信息都掌握之后再更新子树的就需要把所有子树都算完了在更新父亲。2.而像树上背包这样的问题就需要一个一个的更新，每次都用一个子树更新已经更新完的子树+父亲，最后就可以将这一部分的子树更新完了，再继续往上更新，最后根节点就是答案。

其实上面的两种情况可以总结成一种情况就是一个个子树更新父亲，一般来说第一种情况应用更多，也能解决第二情况的问题，只不过如果符合第二种情况的时候用第二种可以速度更快一点，毕竟你省了一遍循环嘛。

http://blog.csdn.net/angon823/article/details/52334548

顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向： 

    1、叶－>根：在回溯的时候从叶子节点往上更新信息

    2、根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。

    不管是 从叶－>根 还是 从 根 - >叶，两者都是根据需要采用，没有好坏高低之分。

2、树形动态规划的优美之处

树真的是一种特别特别优美的结构！用来做动态规划也简直是锦上添花再美不过的事，因为树本身至少就有“子结构”性质（树和子树）；也本身就具有递归性。所以在树上DP其实是其所当然的事，相比线性动态规划来讲，转移方程更直观，更易理解。

3、难点

   1、和线性动态规划相比，树形DP往往是要利用递归的，所以对递归不熟悉的同学，是一道小小的障碍，说是小小的，因为要去理解也不难。

   2、细节多，较为复杂的树形DP，从子树，从父亲，从兄弟……已经一些小的要处理的地方，脑子不清晰的时候做起来颇为恶心

   3、状态表示和转移方程，也是真正难的地方。做到后面，树形DP的老套路都也就那么多，难的还是怎么能想出转移方程，状压DP、概率DP这些特别的DP应该说做到最后都是这样！

4、补充

   建有向图还是无向图？ 一般来说我们做树DP都是从上往下递归，如果不乱搞是不会从子节点往根节点的遍历的，这时候可以建有向图，只加边一次就可以，对于有“思想洁癖”的人来说，如果加一次边就可以再让他加两次是很难受的。但是有些题目可能很隐蔽的某个地方涉及到从子节点往上访问，就会错的很惨。所以，一般不非常确定建有向图就可的话还是建无向图吧。

正文

暂时分入门，一般、难三个等级，而不分类别。以后做的题目多了再改。

1、入门题

1、HDU 1520 Anniversary party 子节点和父亲节点不能同时选，问最大价值。题解

2、HDU 2196 Computer 求树上每个点能到达的最远距离  题解

2、一般

1、D. Choosing Capital for Treeland 给一个n节点的有向无环图，要找一个这样的点：该点到其它n-1要逆转的道路最少，（边<u,v>，如果v要到u去，则要逆转该边方向）题解

2、Godfather  求树的重心（删除该点后子树最大的最小）题解

3、POJ 3107 Tree Cutting  求删除哪点后子树最的小于等于节点总数的一半 题解

4、POJ 3140 Contestants Division 删除某边后剩余两个分支差值最小是多少 题解

3、难

1、HDU 3586 Information Disturbing 给定一个带权无向树，要切断所有叶子节点和1号节点（总根）的联系，每次切断边的费用不能超过上限limit，问在保证总费用<=m下的最小的limit。题解

2、POJ 3162 Walking Race  一棵n个节点的树。wc爱跑步，跑n天，第i天从第i个节点开始跑步，每次跑到距第i个节点最远的那个节点（产生了n个距离），现在要在这n个距离里取连续的若干天，使得这些天里最大距离和最小距离的差小于M，问怎么取使得天数最多？题解

3、HDU 5834 Magic boy Bi Luo with his excited tree 每个节点有一个价值Vi，每走一次一条边要花费Ci，问从各个节点出发最多能收获多少价值 题解

4、POJ 2152 Fire n个节点组成的树，要在树一些点上建立消防站，每个点建站都有个cost[i]，每个点如果不在当前的点上建站，也要依赖其他的消防站，并且距离不超过limit[i]。求符合上述条件的最小费用建站方案 题解

5、POJ 1741 Tree 求树上距离小于等于K的点对有多少个 题解

列出一些经典问题吧：

1：给出一棵树 每个节点有权值  要求父节点和子节点不能同时取 求能够取得的最大值  (hdu1520)

2：给出一棵树，求离每个节点最远的点的距离 (hdu2196)

3：1>在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中允许攻克M个城堡并获得里面的宝物。但由于         地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。求获得尽量多的宝物应         该攻克哪M个城堡。 (hdu1561)

题解：树形dp+背包 

     2>每个节点有两个值bug和brain，当清扫该节点的所有bug时就得到brain值，只有当父节点被清空时，才可以清扫它          的子节点，而清扫需要一定的人员。给定M个人员，N个结点的树，求最大brain和 (hdu1011)

     3>现在有n个村子，你想要用收买m个村子为你投票，其中收买第i个村子的代价是val[i]。但是有些村子存在从属关                系，如果B从属于A国，则收买了A也意味着买通了B，而且这些关系是传递的。问你最小要付出的代价是多                        少？ (poj3345)

4：1>一棵树，定义每个节点的balance值：去掉这点节点后的森林里所有树的最大节点数。求出最小的balance值和其所           对应的节点编号(poj1655)

     2>给你一棵无向树 T，要求依次去除树中的某个结点，求去掉该结点后变成的森林 T' 中的最大分支。并要求该分支为            去除的结点尽可能少。答案可能有多个，需要按照节点编号从小到大输出 (poj3107)

5：给一棵树, n结点<=1000, 和K< =200,  在这棵树上找大小为k的子树, 使其点权和值最大 (zoj3201)

6：给一个树状图，有n个点。求出，去掉哪个点，使得剩下的每个连通子图中点的数量不超过n/2。如果有很多这样的            点，就按升序输出。n<=10000 (poj2378)

7：一棵n个结点的带权无根树，从中删去一条边，使得剩下来的两棵子树的节点权值之和的绝对值最小，并求出得到的最     小绝对值 (poj3140)

8：给出一些点，有值，给出一些边，然后求去掉一条边后将分成连通的两部分，且两部分的差值最小 (hdu2242)

9：有n个点组成一个树，问至少要删除多少条边才能获得一棵有p个结点的子树 (poj1947)

10：一棵树n<=1000(节点的分支<=8)，Snail在根处，它要找到在某个叶子处的house而其中一些节点上有worm，worm        会告诉它的house是否在这个子树上求Snail最快寻找到house走过路径的期望值 (poj2057)

11：给你一颗苹果树，有N个节点每个节点上都有一个苹果也就是有一个权值，当你经过这个节点是你将得到这个权值，         重复走节点是只能算一次，给你N-1条边。问你只能走K步能得到的最大权值和 (poj2486)

12：一颗二叉苹果树树上结苹果，要求剪掉几棵枝，然后求保留Q根树枝能保留的最多到苹果数 (ural1018)

13：给定一棵树，求最少连多少条边，使得每个点在且仅在某一个环内。 (poj1848)

14：在一棵树形的城市中建立一些消防站，但每个城市有一个最大距离限制，求需要的最小花费 (poj2152)

https://www.jianshu.com/p/bb7e76651118

问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。动态规划就是解决多阶段决策最优化问题的一种思想方法。
阶段：
将所给问题的过程，按时间或空间（树归中是空间，即层数）特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。
状态：
各阶段开始时的客观条件叫做状态。
决策：
当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。 （即孩子节点和父亲节点的关系）
策略：
由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。
状态转移方程：
前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段（在树中是孩子节点和父亲节点）状态的演变规律，称为状态转移方程。
目标函数与最优化概念：
目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。
树的特点与性质：
1、 有n个点，n-1条边的无向图，任意两顶点间可达
2、 无向图中任意两个点间有且只有一条路
3、 一个点至多有一个前趋，但可以有多个后继
4、 无向图中没有环；

判断是否是一道树规题：即判断数据结构是否是一棵树，然后是否符合动态规划的要求。如果是，那么执行以下步骤，如果不是，那么换台。

建树：通过数据量和题目要求，选择合适的树的存储方式。如果节点数小于5000，那么我们可以用邻接矩阵存储，如果更大可以用邻接表来存储(注意边要开到2*n，因为是双向的。这是血与泪的教训)。如果是二叉树或者是需要多叉转二叉，那么我们可以用两个一维数组brother[]，child[]来存储（这一点下面会仔细数的）。

写出树规方程：通过观察孩子和父亲之间的关系建立方程。我们通常认为，树规的写法有两种：
a.根到叶子: 不过这种动态规划在实际的问题中运用的不多。
b.叶子到根: 既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多。
注意：这两种写法一般情况下是不能相互转化的。但是有时可以同时使用具体往后看。
以下即将分析的题目的目录及题目特点：
1、加分二叉树：区间动规+树的遍历；
2、二叉苹果树：二叉树上的动规；
3、最大利润：多叉树上的动规；
4、选课：多叉树转二叉；
5、选课（输出方案）：多叉转二叉+记录路径；
6、软件安装：判断环+缩点+多叉转二叉；

https://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf
Crucial observation: once v’s color is determined, subtrees can be solved independently

http://wenku.baidu.com/view/5c80d1d026fff705cc170aa6.html
  一、什么是树型动态规划

顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：

1．  根—>叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。

2．  叶－>根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多，下面就介绍一些这类题目和它们的一般解法。

                                                                               二叉苹果树

【题目描述】：

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

【输入格式】：

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

【输出格式】：

剩余苹果的最大数量。

input

5 2

1 3 1

1 4 10

2 3 20

3 5 20

output

21

题中的节点之间具有连带关系，当剪掉节点2后，以它为根的子树都被剪掉了，如果以它为根的子树中有n个分支，m个苹果的话，我们可以称之为完成了剪掉n个树枝的任务，损失了m个苹果。当然我们希望能够得到一个函数f，表示以节点i为根节点的子树中剪掉n个数值所能保留的苹果最多是多少。记做：f(i,n) 

我们可以将这个问题拆分开来，某个以i为根节点的子树包含i.left为根的左子树和以i.right为根的右子树，要完成n个树枝的修剪任务，只能将n颗树枝的任务分配个这两个子树来完成，就有：     F(i,n)=max(F(i.left,n-j)+ F(i.right, j))(j=0,…n)

    or a(I,j):=max(a(i.left,k)+a(i.right,j-k)),0<=k<=j

【算法&思路】：首先，可以肯定的是，这是一道有关树规的题目，父节点和子节点存在着相互关联的阶段关系。

　　第一步完成。再执行第二步：我们观察到题目数据量不大,所以有两种选择：邻接矩阵和邻接表。因为邻接矩阵的代码简单，思路清晰，所以建议能写邻接矩阵的时候就不要写邻接表了。我们设ma[x][y]为边的值，因为树是双向的，所以要再记录ma[y][x]。

　　设tree[v,1]为节点v的左子树，tree[v,2]为节点v的右子树,然后我们再递归建树（因为树是递归定义的，所以很多时候建树都要考虑递归）

建树的问题解决的了，我们就要列状态转移方程了。根据求什么设什么的原则，我们定义f[i][j]表示以i为节点的根保留k条边的最大值，那么f[v][k]=max(f[v][k],(f[tree[v][1]][i]+f[tree[v][2]][k-i-1]+num[v])),我们枚举i就可以了。正如我开头提到的。因为树是递归定义的所以我们可以用记忆化搜索的形式（dfs）来具体实现。而树本身严格分层，而且没有环。所以是不会重复的。

F[1][Q+1]就是答案。因为题目中给的是边的权值，而我们在处理时将每条边的权值全赋给其所连的父节点和子节点中的子节点（将关于边的问题转化为关于点的问题），所以最后是Q+1，表示点的数目。

在树的存储结构上，我们一般选的都是二叉树，因为二叉树可以用静态数组来存储，并且状态转移也很好写（根节点只和左子节点和右子节点有关系）。

const int ee=105;
17 int n,q;
18 int tree[ee][5]={0},ma[ee][ee]={0},num[ee]={0},f[ee][ee]={0};
20 void preproccess()
21 {
22     for(int i=0;i<=n;i++)
23         for(int j=0;j<=n;j++)
24         {
25             ma[i][j]=-1;
26             ma[j][i]=-1;
27         }
28 }
32 void build(int x,int y,int lor)//lor means left or right
33 {
34     num[y]=ma[x][y];
35     tree[x][lor]=y;
36     ma[x][y]=-1;ma[y][x]=-1;
37     maketree(y);
38 }
40 void maketree(int v)
41 {
42     int lr=0;
43     for(int i=0;i<=n;i++)
44         if(ma[v][i]>=0)//如果分叉了，那么记录
45         {
46             lr++;//1 or 2 表示左支还是右支；
47             build(v,i,lr);//存入并递归
48             if(lr==2)    return;
49         }
50 }
52 void dfs(int v,int k)
53 {
54     if(k==0)    f[v][k]=0;
55     else if(tree[v][1]==0 && tree[v][2]==0) f[v][k]=num[v];
56     else
57     {
58         f[v][k]=0;
59         for(int i=0;i<k;i++)
60         {
61             if(f[tree[v][1]][i]==0)    dfs(tree[v][1],i);
62             if(f[tree[v][2]][k-i-1]==0)    dfs(tree[v][2],k-i-1);
63             f[v][k]=max(f[v][k],(f[tree[v][1]][i]+f[tree[v][2]][k-i-1]+num[v]));
64         }
65     }
66 }   
68 int main()
69 {
72     cin>>n>>q;
73     preproccess(); 
75     for(int i=0;i<n;i++)
76     {
77         int x,y,xy;
78         scanf("%d%d%d",&x,&y,&xy);
79         ma[x][y]=xy;
80         ma[y][x]=xy;
81     }
84     maketree(1);
86     dfs(1,q+1);
88     cout<<f[1][q+1];
91     return 0;
92 }

信息学竞赛中通常会出现这样的问题：给一棵树，要求以最少的代价（或取得最大收益）完成给定的操作。有很多问题都是在树和最优性的基础上进行了扩充和加强，从而变成了棘手的问题。  这类问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优解，因此要用动态规划解决。 

树型动态规划

树型动态规划就是在“树”的数据结构上的动态规划，树型动态规划是建立在树上的，所以有二个方向： 1．根—>叶：这种题目基本上碰不到 2．叶－>根：根的子节点传递有用的信息给根，完后根得出最优解的过程。这种的题目是树型动态规划的最常见类型。 首先定义

       无根树：题目中可以以任意节点为根建树，经过动态规划后即可直接得到最优值。
       有根树：必须以某一个节点为根建树才能通过动态规划后得到最优值。

基本上有这样一个步骤：

一、有根树：

      1.建树（一般以递归方式实现，有时数据过大以BFS方式实现）

      2.在建树中找到叶子的时候特别赋值。

      3.回溯时通过方程确定出每个节点的最优值并记录。

      4.遍历完整棵树后一般以根节点值作为最终值。

补充:关于建树，有很多时候会将原来的多叉树改造为左孩子右兄弟的二叉树，以下两道例题用到了这种改造。

例题1:Tyvj P1051 选课

例题2:Vijos P1518 河流(IOI2005 Rivers)

--澹台彦澍 02:08 2009年9月8日 (CST)

//简单的改造代码:
        for i:=1 to n do
            if ft[root[i]]=false then//这个节点目前还没有孩子
                begin
                  a[root[i]].left:=i;//把这玩意儿放到当前节点的左边
                    ft[root[i]]:=true;//标记-有孩子了
                    num[root[i]]:=i;//该节点当前最后一个孩子
                end
            else//有孩子了
                begin
                  a[num[root[i]]].right:=i;//把这玩意儿给他当前最后一个孩子的右边
                     num[root[i]]:=i;
              end;//By 澹台彦澍

二、无根树：

      1.随机定根，重复有根树过程
      2.要枚举节点作为根的情况重复有根树过程。

例题:Vijos P1100 加分二叉树(NOIp2003第三题)

http://www.cnblogs.com/gq-ouyang/archive/2013/02/26/2933431.html
之所以这样命名树规，是因为树规的这一特殊性：没有环，dfs是不会重复，而且具有明显而又严格的层数关系。利用这一特性，我们可以很清晰地根据题目写出一个在树（型结构）上的记忆化搜索的程序。而深搜的特点，就是“不撞南墙不回头”。

拿到一道树规题，我们有以下3个步骤需要执行：

1. 判断是否是一道树规题：即判断数据结构是否是一棵树，然后是否符合动态规划的要求。如果是，那么执行以下步骤，如果不是，那么换台。
2. 建树：通过数据量和题目要求，选择合适的树的存储方式。如果节点数小于5000，那么我们可以用邻接矩阵存储，如果更大可以用邻接表来存储(注意边要开到2*n，因为是双向的。这是血与泪的教训)。如果是二叉树或者是需要多叉转二叉，那么我们可以用两个一维数组brother[]，child[]来存储（这一点下面会仔细数的）。
3. 写出树规方程：通过观察孩子和父亲之间的关系建立方程。我们通常认为，树规的写法有两种：

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

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

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即可。接下来是如何建树的问题，只有把树建好了，才能输出其前序遍历。于是，我们看到了两个关键词：二叉树，中序遍历。有了这两个关键词，加上区间动规，这棵树就能建起来了。

题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点，用数组root[i,j]表示

16 const int ee=50,e=-999999999;
17 int n;
18 int a[ee]={0},f[ee][ee],root[ee][ee]={0};//f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分
19 
20 //**若根节点的下表是k，则左端点的是k-1，右端点是k+1；
21 void front(int x,int y)
22 {
23     if(root[x][y]!=0)
24         cout<<root[x][y]<<' ';
25     if(root[x][root[x][y]-1]!=0)    front(x,root[x][y]-1);
26     if(root[root[x][y]+1][y]!=0)    front(root[x][y]+1,y);
27 }
29 int main()
30 {
35     cin>>n;
37     for(int i=0;i<=n;i++)
38     {
39         for(int j=0;j<=n;j++)
40             f[i][j]=1;
41     }
42     for(int i=1;i<=n;i++)
43     {
44         cin>>a[i];
45         f[i][i]=a[i];
46         root[i][i]=i;
47     }
48     //区间长度
49     for(int len=1;len<=n;len++)
50     {
51         //区间起点
52         for(int i=1;i<=n;i++)
53         {
54             //终点
55             int j=i+len;
56             if(j<=n)
57             {
58                 int temp=e;
59                 //因为是中序排列
60                 for(int k=i;k<=j;k++)
61                 {
62                     if(temp < (f[i][k-1]*f[k+1][j]+a[k]))
63                     {
64                         temp=f[i][k-1]*f[k+1][j]+a[k];
65                         root[i][j]=k;
66                     }
67                 }
68                 f[i][j]=temp;
69             }
70         }
71     }
72     cout<<f[1][n];
74     //前序遍历
75     cout<<endl;
76     front(1,n);
79 fclose(stdin);fclose(stdout);
80 return 0;
81 }

3、最大利润

【题目描述】

政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。
告诉你每个火车站的利润，问你可以获得的最大利润为多少。
最佳投资方案是在1，2，5，6这4个火车站开饭店可以获得利润为90

【输入格式】

第一行输入整数N(<=100000)，表示有N个火车站，分别用1，2。。。，N来编号。接下来N行，每行一个整数表示每个站点的利润，接下来N-1行描述火车站网络，每行两个整数，表示相连接的两个站点。

【输出格式】

输出一个整数表示可以获得的最大利润。

首先，这是棵树，是一棵多叉树。其次，当我们尝试着把他向动态规划上靠时，我们发现当前节点只与其孩子节点的孩子节点（这里没打错，因为隔一个火车站）有关系。所以综上所述，是动规，还是一个树规，一个不折不扣的树规！

　　接下来，第二步建树。看范围和题目发现，这是一个有着n（<100000）的多叉树，所以只能用邻接表存储了。没有根，我们一般通常指定1为根。

　　第三步：F[i]表示i这条根要，G[i]表示不要（也可以用f[i][1,0]来表示）。然后以此枚举i的孩子：如果i要了那么i的孩子就不能要，如果i不要i的孩子就可要可不要（取最大值）即可。最后输出max（f[1],g[1]）;

无论是多叉树还是二叉树，只要我们把树以正确的形式建立起来，那么我们再根据建树的形式和题目要求，找出孩子和父亲之间的关系，那么状态转移方程很容易就求解出来了。多叉其实也不是很难。对么？呵呵，那么再看下面一道题：

16 const int e=100020;
17 int f[e]={0},g[e]={0},a[e]={0},link[e]={0};//f[i]表示这条根要，g【i】表示不要；
18 int n,t=0;
20 struct qq
21 {
22     int y,next;
23 }ee[2*e];
25 void insert(int startt,int endd)    //临界表存储树
26 {
27     ee[++t].y=endd; ee[t].next=link[startt];
28     link[startt]=t;
29 }
31 void dfs(int root,int father)
32 {
33     int tempf=0,tempg=0;
34     for(int i=link[root];i;i=ee[i].next)
35     {
36         if(ee[i].y!=father)
37         {
38             dfs(ee[i].y,root);
39             f[root]+=g[ee[i].y];
40             g[root]+=max(f[ee[i].y],g[ee[i].y]);
41         }
42     }
43     f[root]+=a[root];
44 }
46 int main()
47 {
49     cin>>n;
50     for(int i=1;i<=n;i++)
51         scanf("%d",&a[i]);
53     for(int i=1;i<n;i++)
54     {
55         int xx,yy;
56         scanf("%d%d",&xx,&yy);
57         insert(xx,yy);
58         insert(yy,xx);
59     }
61     dfs(1,1);
63     cout<<max(f[1],g[1]);
65 fclose(stdin);fclose(stdout);
66 return 0;
67 }     

4、选课多叉转二叉

【题目描述】

　　学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。
　　在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。

　你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

输入文件的第一行包括两个整数N、M（中间用一个空格隔开），其中1≤N≤300,1≤M≤N。
以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

继续照着三步的方法判断：一，题目大致一看，有点像有依赖的背包问题，于是你扭头就走，关掉了我的《树规》，打开了崔神犇的《背包九讲》。然后你哭了，因为有依赖的背包问题只限定于一个物品只依赖于一个物品，而没有间接的依赖关系。有依赖的背包问题的模型，根本解决不了。崔神告诉你，这属于树规的问题，不属于他背包的范围了。好了，回过来，我们接着分析。发现这是一棵树，还是一棵多叉树，嗯，很好，确定是树规了。

输入文件的第一行包括两个整数N、M（中间用一个空格隔开），其中1≤N≤300,1≤M≤N。
以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

　　然后第二步，建树，一看数据范围邻接矩阵；

　　第三步动规方程：f[i][j]表示以i为节点的根的选j门课的最大值，然后有两种情况： i不修，则i的孩子一定不修，所以为0；i修，则i的孩子们可修可不修（在这里其实可以将其转化为将j-1个对i的孩子们进行资源分配的问题，也属于背包问题）；答案是f[1][m]。问题圆满解决，一气呵成。

身为追求完美的苦*程序猿的我们，不可以将它更简单一点呢？

　　多叉转二叉。

　　因为之前我们说过“在树的存储结构上，我们一般选的都是二叉树，因为二叉树可以用静态数组来存储，并且状态转移也很好写（根节点只和左子节点和右子节点有关系）。”所以转换成二叉树无疑是一种不错的选择。

　　我们开两个一维数组，b[i](brother)&c[i](child)分别表示节点i的孩子和兄弟，以左孩子和右兄弟的二叉树的形式存储这样，根节点之和两个节点有关系了，状态转移的关系少了，代码自然也就好写了。

　　我们依旧f[i][j]表示以i为节点的根的选j门课的最大值，那么两种情况：1.根节点不选修则f[i][j]=f[b[i]][j];2.根节点选修f[i][j]=f[c[i]][k]+f[b[i]][j-k-1]+a[i]（k表示左孩子学了k种课程）;取二者的最大值即可。

当题目中的数据结构是多叉树的时候，我们有两种选择：直接在多叉树上动规，或者转化为二叉树后动规。毫无疑问，二叉树上的动规是简洁的。但是，并不是说所有的多叉树都需要转化，一般情况下，当根节点与孩子节点有着必然的关系时才会转化。这需要我们多做题目，增加对树规的感觉才能游刃有余。

16 const int e=320;
17 int n,m;
18 int c[e]={0},b[e]={0},s[e]={0},f[e][e]={0};//c[]:means child ; b[]:means brother
20 void maketree()//多叉转二叉
21 {
22     cin>>n>>m;
23     for(int i=1;i<=n;i++)
24     {
25         int ta,tb;
26         scanf("%d%d",&ta,&tb);
27         s[i]=tb;
28         if(ta==0) ta=n+1;
29         b[i]=c[ta];
30         c[ta]=i;
31     }
32 }
34 void dfs(int x,int y)
35 {
36     if(f[x][y]>=0)    return;
37     if(x==0 || y==0) {  f[x][y]=0;return;}
38     dfs(b[x],y);
39     //max()f[b[x]][y];
40     for(int k=0;k<y;k++)
41     {
42         dfs(b[x],k); //不取根节点
43         dfs(c[x],y-k-1);//取根节点
44         f[x][y]=max(f[x][y] , max(f[b[x]][y] , f[b[x]][k]+f[c[x]][y-k-1]+s[x]));
45     }
47     return;
48 }
50 int main()
51 {
54     memset(f,-1,sizeof(f));
56     maketree();
57     dfs(c[n+1],m);
59     cout<<f[c[n+1]][m]<<endl;
61 fclose(stdin);fclose(stdout);
62 return 0;
63 }  

5、选课（输出方案）：多叉转二叉+记录路径；

6、软件安装：判断环+缩点+多叉转二叉；

【4、5、6属于依赖问题的变形】