若水而净万物

题目一：道路重建(USACO_2002_Feb02 Rebuilding Roads)（PKU1947）(程序附后)
题目大意是给一棵树，要去掉最少的边，使一棵子树从中分离出来，且这棵子树要恰有B个节点。

很容易想到此题为树型Dp,用状态[i,j]来表示以节点i为根，得到一棵j个节点的子树至少要去多少条边（请注
意，这里定义的节点i是这棵子树的根,所以一定包含这棵去掉一些边后所得到的j个节点的子树里面）。怎么
转移呢？如果穷举i的子节点保留还是不保留，如果保留，保留多少个。那么这道题目又退化成完全的搜索了。。不难想到,因为节点i的所有子节点是一个线性结构,我们可以双重Dp!!

下面讲一下第二重的Dp:
对于一个节点i,
设它的儿子依次为1,2,....,x.再设一个状态(k,m)表示到节点i的第k个儿子,要保留m个节点,至少要去掉多少条边.这样,对于这个节点i,我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是选这个k,二是不选这个k,
1.如果不选k,那么(k-1,m)+1--->(k,m)(加1是因为不选这个儿子k,所以k和i所连的边应该断开,那么花费就要加1).
2.如果选nk,那么(k-1,j)+[k,m-j]--->(k,m)(注意,中括号所表示的状态时第一重动规所得到的状态,在这里[k,m-j]的意思就是节点k为根，得到一棵(m-j)个节点的子树至少要去多少条边)

那么就很容易转移了:(k,m)=min{(k-1,j)+[k,m-j]{0<=j<=m},(k-1,m)+1},边界自己想吧。。。。。对于这个节点i,算完所有的(1,m),(2,m),...,(x,m)后,[i,m+1]就等于(x,m)(这里+1是因为i这个节点要保留),每次算出(i,B)后,动态更新下ans就行了...Dp时候的顺序可以记忆化搜索,也可以按后序遍历的顺序进行Dp...

尽管讲了这么多,感觉还是有很多细节问题没有讲清楚,这还是要自己思考一下的,这里只是提供了一个大致的
思路而已...(更多时候，这个思路可能只有作者本人才能看懂的--!)。如果谁有更好的方法,欢迎留言:)

题目二： 贪吃的九头龙（NOI2002_DAY1）
题目大意是给一棵树，再给m种点，这些点要覆盖这棵树的所有节点，且每种种类的点至少要用一次，还规定第一种点必须恰好用K次。这棵树的每一条边都有一个权值（每条边的权值可能不同）。对于某条边，若这条边的两个顶点种类相同，则总权值需要加上这条边的权值。问总权值最少是多少。（可能描述的有些模糊，不懂的看一下原题吧。。。）

首先，要明确一点，就是除了m=2的情况外，如果有的边的两个顶点种类相同，那么这种种类一定是第一种！这能保证解是最优的！发现了这个，就意味着问题解决了一半了。接下来就是状态表示了。。
不难想到用[i,j]表示节点i，恰有j个节点被第一种类的点覆盖，总权值最小是多少。不！这还不够！我们必
须增加一维！这一维不是0就是1，0表示节点i被第一种类的点覆盖，1表示节点i被非第一种类的点覆盖（就是被第二或第三...或第m种类的点覆盖啦--！）。即状态是[i，j，0/1]怎么转移？这不禁联想到上面的第一题，如果还是这样进行一重Dp,那也就是退化成单纯的搜索了。。我们必须进行双重Dp!!

下面还是讲一下第二重的Dp:
还是和上题一样，对于一个节点i，它是0或1类型的。这里只举0类型的例子（即不妨假设节点i被第一种类的点覆盖）。我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是这个儿子类型是0,二是这个儿子的类型是1。
转移就不细讲了。因为涉及到很多很多的细节问题，并且不把这些细节问题讲清楚的话，转移就讲不清楚。而讲清楚这些细节问题至少需要1000+个字。所以就不详细展开讲了。。。。-_-！-_-！-_-!。。。。

总结一下。这两道题都是TreeDp,都是需要双重Dp.可以说,它们两的本质是相同的.可是,不同在哪呢?为什么第二题《贪吃的九头龙》要再加一维呢?深入思考,可以看出它们两的转移方式不同,即option不同.对于第一题,转移的时候是对边而言选还是不选的.对于第二题,转移的时候是对点而言选0类型还是选1类型.而状态是记录在点上,而不是记录在边上.所以第一题只要二维而第二题要三维.换句话说,如果我们表示状态的时候把状态记录在边上,那么第二题只要二维而第一题要三维了。上述的一段话正是本文想要说明的关键部分，有些问题虽然形式不同，但本质相同，所以只有把握本质，深入思考，才能豁然开朗。。。。。

刚搞到一个code_to_html的软件Highlight Code Converter，效果感觉不错：）。故把上述第一题的代码附上。

P.S.第二题我写了7KB,很烂,所以不发上来了.

CODE:                                                 

..........