树的动态规划与构造广东北江中学薛矛【关键字】树的动态规划上方子树树的构造【摘要】本文通过几道关于树的题目，分析了树的动态规划与构造这两种类型题目的解法。【目录】TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc67561301"一、树的动态规划PAGEREF_Toc67561301\h2HYPERLINK\l"_Toc67561302"『例1』CentroidPAGEREF_Toc67561302\h2HYPERLINK\l"_Toc67561303"『例2』ComputerNetworkPAGEREF_Toc67561303\h3HYPERLINK\l"_Toc67561304"『例3』数据生成器PAGEREF_Toc67561304\h5HYPERLINK\l"_Toc67561305"『例4』PAGEREF_Toc67561305\h7HYPERLINK\l"_Toc67561306"小结PAGEREF_Toc67561306\h7HYPERLINK\l"_Toc67561307"二、树的构造PAGEREF_Toc67561307\h8HYPERLINK\l"_Toc67561308"『例5』PAGEREF_Toc67561308\h8HYPERLINK\l"_Toc67561309"『例6』树重建(Rebuild)PAGEREF_Toc67561309\h9HYPERLINK\l"_Toc67561310"『例7』毛毛虫(Caterpillar)PAGEREF_Toc67561310\h10HYPERLINK\l"_Toc67561311"三、总结PAGEREF_Toc67561311\h12【正文】树，是一种很特殊的数据结构，关于它的题目十分的多，几乎在大部分的比赛当中都会出现这类型的题目，而且研究树的题目也是十分有趣的。由于以树为背景，题目会很明显地渗透了树的特征，而树的特征也正是我们解决这类问题的突破口。树的问题往往会有一个十分突出的特点：数据量十分大。由于树是十分特殊的图：连通图，n个顶点，n-1条边。因此在空间可以承受的范围内n可以达到很大。而且树的特殊结构也决定了算法的优越性。正因为树的特殊，通常能够找到十分高效的算法（比如说是O(n)）。于是我们解决这类题目的时候应当牢牢抓住树的特征，认真分析问题，这样就能比较好地解决题目了。下面举一些例子谈谈树的动态规划与构造。一、树的动态规划树的动态规划，顾名思义，就是在树上面进行动态规划。树的动态规划很有特点，虽说对某个结点来说，状态转移的复杂度是不确定的（这取决于与它相连的边数），但是总体来说，每条边通常只会对应常数次状态转移，所以总的复杂度是O(n)的，这就使树的动态规划十分高效。例如下面这道题目：『例1』Centroid题目来源：SGU.ProblemSet134(acm.sgu.ru)Youaregivenanundirectedconnectedgraph,withNverticesandN-1edges(atree).Youmustfindthecentroid(s)ofthetree.Inordertodefinethecentroid,someintegervaluewillbeassosciatedtoeveryvertex.Let'sconsiderthevertexk.Ifweremovethevertexkfromthetree(alongwithitsadjacentedges),theremaininggraphwillhaveonlyN-1verticesandmaybecomposedofmorethanoneconnectedcomponents.Eachofthesecomponentsis(obviously)atree.Thevalueassociatedtovertexkisthelargestnumberofverticescontainedbysomeconnectedcomponentintheremaininggraph,aftertheremovalofvertexk.Alltheverticesforwhichtheassociatedvalueisminimumareconsideredcentroids.InputThefirstlineoftheinputcontainstheintegernumberN(1<=N<=16000).ThenextN-1lineswill