树的动态规划及构造

《树的动态规划及构造》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、【关键字】    树的动态规划 上方子树 树的构造【摘要】   本文通过几道关于树的题目，分析了树的动态规划与构造这两种类型题目的解法。【目录】一、树的动态规划 2『例1』Centroid 2『例2』ComputerNetwork 3『例3』数据生成器 5『例4』 7小结   7二、树的构造 8『例5』 8『例6』树重建(Rebuild) 9『例7』毛毛虫(Caterpillar) 10三、总结   12【正文】   树，是一种很特殊的数据结构，关于它的题目十分的多，几乎在大部分的比赛当中都会出现这类型的题目，而且研究树的题目也

2、是十分有趣的。由于以树为背景，题目会很明显地渗透了树的特征，而树的特征也正是我们解决这类问题的突破口。   树的问题往往会有一个十分突出的特点：数据量十分大。由于树是十分特殊的图：连通图，n个顶点，n-1条边。因此在空间可以承受的范围内n可以达到很大。而且树的特殊结构也决定了算法的优越性。正因为树的特殊，通常能够找到十分高效的算法（比如说是O(n)）。于是我们解决这类题目的时候应当牢牢抓住树的特征，认真分析问题，这样就能比较好地解决题目了。   下面举一些例子谈谈树的动态规划与构造。一、树的动态规划   树的动态规划，顾名思义，

3、就是在树上面进行动态规划。树的动态规划很有特点，虽说对某个结点来说，状态转移的复杂度是不确定的（这取决于与它相连的边数），但是总体来说，每条边通常只会对应常数次状态转移，所以总的复杂度是O(n)的，这就使树的动态规划十分高效。   例如下面这道题目：『例1』CentroidYouaregivenanundirectedconnectedgraph,withNverticesandN-1edges(atree).Youmustfindthecentroid(s)ofthetree.  Inordertodefinethecentr

4、oid,someintegervaluewillbeassosciatedtoeveryvertex.Let'sconsiderthevertexk.Ifweremovethevertexkfromthetree(alongwithitsadjacentedges),theremaininggraphwillhaveonlyN-1verticesandmaybecomposedofmorethanoneconnectedcomponents.Eachofthesecomponentsis(obviously)atree.Thev

5、alueassociatedtovertexkisthelargestnumberofverticescontainedbysomeconnectedcomponentintheremaininggraph,aftertheremovalofvertexk.Alltheverticesforwhichtheassociatedvalueisminimumareconsideredcentroids. InputThefirstlineoftheinputcontainstheintegernumberN(1<=N<=16000)

6、.ThenextN-1lineswillcontaintwointegers,aandb,separatedbyblanks,meaningthatthereexistsanedgebetweenvertexaandvertexb. OutputYoushouldprinttwolines.Thefirstlineshouldcontaintheminimumvalueassociatedtothecentroid(s)andthenumberofcentroids.Thesecondlineshouldcontaintheli

7、stofverticeswhicharecentroids,sortedinascendingorder. SampleInput7122324155667SampleOutput311   题目的意思是说：给出一棵具有N个结点的树(1<=N<=16000)，找出这棵树的“质心”。“质心”的定义如下：对于树中的每个结点K。若将它删去，则一棵树会变为若干棵树，取这些树的结点数中最多的作为结点K的值，若K为树的质心，则结点K的值是所有结点的值中最小的。要你求出树的所有质心。   这是一道关于树的题目。我们要找的其实就是一个结点K，使

8、它所有子树的结点数的最大值最小。我们只需对每一个结点都求出它的每棵子树的结点数，就能求出树的所有质心了。求一棵子树的结点数可以用动态规划来解决。由于题目输入的是一棵无根树，我们可以先随便找一个结点作为根节点，然后对这棵树遍历。用F(A)表示以结点A为根的树的结点