樹的各種問(wèn)題

1、樹的各種問(wèn)題LOI_50 Kudo 周界知識(shí)提綱定義、性質(zhì)、遍歷定義、性質(zhì)、遍歷、多叉轉(zhuǎn)二叉各種例題各種吐槽術(shù)語(yǔ)對(duì)照表ZFQ 臧方青（Otz）ZZC 趙宗昌（Orz）TYVJ 信息學(xué)在線評(píng)測(cè)系統(tǒng)FZOJ 福州大學(xué)Online JudgeSDTDC2011 Round 1 2011年山東省選第一輪 Orz 失意體前驅(qū)，表示膜拜 WS 猥瑣ms 時(shí)間單位，毫秒AC Accepted，題目通過(guò)dxh 神牛的ID一、樹的基本知識(shí)1、樹的定義(基礎(chǔ)部分先粘部分ZFQ的課件) 樹是一種常見的非線性的數(shù)據(jù)結(jié)構(gòu)。樹的遞歸定義如下： 樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件： 有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)

2、（父親結(jié)點(diǎn)），該結(jié)點(diǎn)稱為樹的根； 除根外，其余的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)； 除根外，每一個(gè)結(jié)點(diǎn)都通過(guò)唯一的路徑連到根上（否則有環(huán)）。這條路徑由根開始，而未端就在該結(jié)點(diǎn)上，且除根以外，路徑上的每一個(gè)結(jié)點(diǎn)都是前一個(gè)結(jié)點(diǎn)的后繼（兒子結(jié)點(diǎn)）；由上述定義可知，樹結(jié)構(gòu)沒(méi)有封閉的回路。 一、樹的基本知識(shí)2、樹的表示法 (1)自然界樹形表示法（一般用于分析問(wèn)題） 比如說(shuō)這種： (2)括號(hào)表示法 先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹按由左而右的順序放入括號(hào)中，而對(duì)子樹也采用同樣方法處理：同層子樹與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹之間用逗號(hào)隔開，最后用閉括號(hào)括起來(lái)。例如圖可寫成如下形式一、樹的基本知識(shí)(

3、a)(a,(b,c)(a,(b(d,e),c)值得注意的是，有些題目中雖然沒(méi)有很裸露的說(shuō)是樹，但是隱含條件就能表明它是一棵樹。如：有n個(gè)節(jié)點(diǎn)，有n-1條邊，每?jī)蓚€(gè)點(diǎn)間只有一條邊，這就是一棵樹。比如說(shuō)TYVJP1331（sdlwwlp分餅）有些情況下，樹會(huì)變成一條鏈。比如SDTSC2011Round 1的第三題在樹上的操作，30%的數(shù)據(jù)是一條鏈，可以將它看作區(qū)間用線段樹處理。但是要過(guò)掉此題，只要用一種叫樹鏈剖分的神奇的東西（%#果斷略過(guò)）3、樹的遍歷 其實(shí)這種東西很水，以至于ZFQ在夏令營(yíng)的時(shí)候完全沒(méi)有提到。但是ZZC在講解廣搜的地方略有提到。因?yàn)闃洳皇嵌鏄?，所以樹的遍歷也許要用到以下兩種方式

4、。一、樹的基本知識(shí)一、樹的基本知識(shí)推薦題目（TYVJP1033 悠閑的漫步） Bessie透過(guò)牛棚的大門向外望去。發(fā)現(xiàn)今天是一個(gè)美麗的春季早晨。她想，“我真的好想好想沐浴著春風(fēng)，走在草地之中，感受嫩草溫柔地?fù)崦奶愕氐母杏X(jué)。”她知道一旦她離開了牛棚，她將沿著一條小徑走一段路，然后就會(huì)出現(xiàn)一個(gè)三岔路口，她必須在兩條小徑中選擇一條繼續(xù)走下去。然后她又會(huì)遇到更多的三岔路口，進(jìn)行更多的選擇，知道她到達(dá)一個(gè)青翠的牧場(chǎng)為止。 她決定坐一個(gè)選擇使得她在去吃早草的路途中可以走過(guò)最多的小徑。給你這些小徑的描述，要求Bessie最多可以走過(guò)多少條小徑。假定Bessie一出牛棚就有2條路徑，Bessie需要從中選擇

5、一條。 農(nóng)場(chǎng)中有P-1 (1 = P = 1,000) 個(gè)分岔節(jié)點(diǎn)（范圍是1.P），引向P片草地，它們之間由小徑連接。對(duì)任意一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，只有一條從牛棚（被標(biāo)記為節(jié)點(diǎn)1）開始的路徑可以到達(dá)。 考慮下面的圖。線段表示小徑，%表示草地。右邊的圖中的#表示一條到達(dá)草地的高亮的路徑。一、樹的基本知識(shí) % % / / 2-% 7-8-% 2-% 7#8-% / / # # # # 1 5-69-% 1 5#69-% # % % 3-% 3-% 4-%4-% % % 從分岔節(jié)點(diǎn)9到達(dá)的草地是兩個(gè)可以讓Bessie走過(guò)最多小徑的草地之一。在去吃早草的路上Bessie將走過(guò)7條不同的小徑。這些草地是離牛棚也就

6、是節(jié)點(diǎn)1最“遠(yuǎn)”的。 由3個(gè)整數(shù)來(lái)表示每一個(gè)節(jié)點(diǎn)：Cn, D1和D2，Cn是節(jié)點(diǎn)的編號(hào)(1 = Cn = P-1); D1和D2是由該節(jié)點(diǎn)引出的兩條小徑的終點(diǎn)(0 = D1 = P-1; 0 = D2 = P-1)。如果D1為0，表示這條小徑引向的是一片牧草地；D2也一樣。一、樹的基本知識(shí)輸入格式 Input Format * 第1行: 一個(gè)單獨(dú)的整數(shù): P * 第2到第P行: 第i+1行有3個(gè)由空格隔開的整數(shù)，表示一個(gè)分岔節(jié)點(diǎn)Cn, D1和D2。輸出格式 Output Format * 第一行: 一個(gè)單獨(dú)的整數(shù)，表示Bessie去最遠(yuǎn)的草地的路上最多可以走過(guò)的小徑的數(shù)目。二、二叉樹基本知識(shí)1

7、 1、二叉樹的定義（繼續(xù)引用、二叉樹的定義（繼續(xù)引用.） 二叉樹是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，且其子樹有左右之分（有序樹，次序不能任意顛倒）。 二叉樹是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件： 有一個(gè)特定的結(jié)點(diǎn)稱為根； 余下的結(jié)點(diǎn)分為互不相交的子集L和R，其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹；這樣很顯然會(huì)有一個(gè)問(wèn)題：二叉樹是樹?二叉樹不是樹？二叉樹是果樹？樹是二叉樹？ 二叉樹不是樹！二、二叉樹基本知識(shí) 一些解釋：由上述定義可以看出，二叉樹和樹是兩個(gè)不同的概念+樹的每一個(gè)結(jié)點(diǎn)可以有任意多個(gè)后件，而二叉樹中每個(gè)結(jié)點(diǎn)的后繼不能超過(guò)2；樹的

8、子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結(jié)點(diǎn)的左后件為左兒子，右后件為右兒子。綜上所述：二叉樹不是樹。雖然有一些相似性，但它們是兩個(gè)不同的概念。二、二叉樹基本知識(shí)二叉樹的兩個(gè)特殊形態(tài)滿二叉樹： 如果一棵深度為K的二叉樹，共有2K-1個(gè)結(jié)點(diǎn)，即第I層有2I-1的結(jié)點(diǎn)，稱為滿二叉樹。（左圖）完全二叉樹：如果一棵二叉樹最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹。（右圖）二、二叉樹基本知識(shí)2、性質(zhì) 二叉樹有三個(gè)比較給力的性質(zhì)，在各種關(guān)于二叉樹的討論中不時(shí)會(huì)用到，所以要熟練掌握。證明 數(shù)學(xué)歸納法證明歸

9、納基礎(chǔ) i=1時(shí)，有2(i-1)=20=1,因?yàn)榈谝粚又挥幸粋€(gè)根結(jié)點(diǎn)，所以命題成立。歸納假設(shè) 假設(shè)對(duì)于所有的j（1=ji）命題成立，即第j層上至多有2(j-1)個(gè)結(jié)點(diǎn)，證明j=i時(shí)命題亦成立。歸納步驟 根據(jù)歸納假設(shè)，第i-1層的結(jié)點(diǎn)數(shù)至多是第2(i-2)個(gè)結(jié)點(diǎn)。由于二叉樹的每個(gè)結(jié)點(diǎn)至多有2個(gè)孩子，故第i層上至多有2*2(i-2)=2(i-1)個(gè)結(jié)點(diǎn)。性質(zhì)1：在二叉樹的第i（1）層上，最多有2(i-1)個(gè)結(jié)點(diǎn)二、二叉樹基本知識(shí)性質(zhì)2：在深度為k(k1)的二叉樹中最多有2k-1個(gè)結(jié)點(diǎn)。證明：根據(jù)性質(zhì)1，深度為k的二叉樹最多有：20+21+.+2k-1=2k-1（等比數(shù)列求和乘2做減法）。性質(zhì)3：在

10、任何二叉樹中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。即 n0=n2+1設(shè)n0為二叉樹的葉結(jié)點(diǎn)數(shù)；n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)；n2為二叉樹中度為2的結(jié)點(diǎn)數(shù)，顯然 所有結(jié)點(diǎn)數(shù)目 n=n0+n1+n2 （1）所有這些分支同時(shí)又為度為1和度為2的結(jié)點(diǎn)發(fā)出的。再加上根結(jié)點(diǎn)，因此又有 n=1+n1+2n2 (2)由上兩個(gè)等式求得：n0=1+n2二、二叉樹基本知識(shí) 例題：如果一棵m度的樹中有N1個(gè)度為1的頂點(diǎn)，N2個(gè)度為2的頂點(diǎn)，N3個(gè)度為3的頂點(diǎn)，Nm個(gè)度為m的頂點(diǎn)，求該樹中葉子頂點(diǎn)個(gè)數(shù)。因?yàn)闃渲泄?jié)點(diǎn)個(gè)數(shù)有兩種不同的表達(dá)方式，所以我們?cè)诖藢で蟮攘筷P(guān)系。1、總結(jié)點(diǎn)數(shù)=N0+N1+N2+.+Nm2、總結(jié)點(diǎn)數(shù)=1*

11、N1+2*N2+.+m*Nm+1二者相等可得：N0 =N2+2N3+3N4+.+(M-1)NM+1二、二叉樹基本知識(shí)3、遍歷 因?yàn)槎鏄涞奶厥庑?，所以不用像樹的遍歷一樣繁瑣，只需根據(jù)其定義擴(kuò)展左右兒子即可。用簡(jiǎn)單的遞歸（dfs）即可實(shí)現(xiàn)。 但是在遍歷的過(guò)程中，又衍生出了三種不同的遍歷方法：前序遍歷、中序遍歷、后序遍歷。 誰(shuí)能簡(jiǎn)述一下這三種遍歷？設(shè)L 左兒子 R 右兒子 D 根節(jié)點(diǎn)則前序遍歷 DLR 中序遍歷 LDR 后序遍歷 LRD可以發(fā)現(xiàn)，其根據(jù)根節(jié)點(diǎn)被訪問(wèn)的順序而命名。二、二叉樹基本知識(shí)4、森林、樹和二叉樹的轉(zhuǎn)化 在處理許多題目時(shí)，題目中給出的條件是一個(gè)森林（一坨樹），而我們可以在一棵樹上

12、解決問(wèn)題的時(shí)候，可以采用這個(gè)方法： 加入一個(gè)虛根，把所有樹的根節(jié)點(diǎn)與這個(gè)節(jié)點(diǎn)相連構(gòu)成一棵樹再進(jìn)行有關(guān)操作。示意如下：二、二叉樹基本知識(shí) 有些時(shí)候，為了使問(wèn)題更簡(jiǎn)單，還需要把樹轉(zhuǎn)換成二叉樹，這樣利用二叉樹的有關(guān)性質(zhì)也許會(huì)有意想不到的收獲！ 但是，把多叉樹轉(zhuǎn)換成二叉樹既需要完整地保存原樹的信息，而且在使用的時(shí)候還應(yīng)該便于知道兩個(gè)點(diǎn)之間的關(guān)系。我們需要這樣一種思想，即“左兒子右兄弟”。對(duì)于一個(gè)點(diǎn)，把他的兒子（中的一個(gè)）當(dāng)作左兒子，把他的兄弟（我不說(shuō)是一個(gè)）當(dāng)作他的右兒子。二、二叉樹基本知識(shí)于是，在這個(gè)課件中，我們將看到第一段代碼：read(v,u); u是v的兒子readln(au); u點(diǎn)的信息i

13、f leftv=0 then leftv:=u else 如果v沒(méi)有左兒子beginrightu:=leftv; leftv:=u; end; v有左兒子，那么u就是v左兒子的兄弟，就把u的右兒子設(shè)為leftv可以看出，我們?cè)谧x入的過(guò)程中就十分犀利的解決了這個(gè)看似復(fù)雜的問(wèn)題。以后遇到這種問(wèn)題我們就可以隨便轉(zhuǎn)化了。三、樹形動(dòng)態(tài)規(guī)劃下面，在經(jīng)過(guò)漫長(zhǎng)的鋪墊之后，終于進(jìn)入了原創(chuàng)時(shí)間我們通過(guò)一些經(jīng)典題目來(lái)研究一下在樹上的動(dòng)態(tài)規(guī)劃。我們知道，線性動(dòng)態(tài)規(guī)劃往往要根據(jù)題目中提供的某些順序來(lái)滿足動(dòng)態(tài)規(guī)劃的無(wú)后效性。例如01背包中的物品件數(shù)，石子合并的區(qū)間長(zhǎng)度等等。而圖上的動(dòng)歸往往沒(méi)有現(xiàn)成的順序，一般要經(jīng)過(guò)拓?fù)渑?/p>

14、序得到序列之后才能進(jìn)行一些操作。而更復(fù)雜一些的往往要用tarjan縮點(diǎn)然后dp。例如Lex神犇講解的tarjan+DP的最優(yōu)貿(mào)易。而在樹上的動(dòng)態(tài)規(guī)劃，不需要tarjan神馬的（因?yàn)闃渖蠜](méi)有環(huán)這個(gè)果斷不解釋）。但是還是要滿足動(dòng)歸的無(wú)后效性，所以一般都是以遍歷的序列來(lái)做一些事情。樹形動(dòng)態(tài)規(guī)劃規(guī)劃在考試中時(shí)有出現(xiàn)，所以我們有必要研究一下。去年暑假LOI校內(nèi)考試的最后一題拾金子?。ê萌醅F(xiàn)在才知道）在NOIP中樹形動(dòng)歸最經(jīng)典的是03年的加分二叉樹，據(jù)說(shuō)06年能量項(xiàng)鏈，06金明的預(yù)算方案也能用樹規(guī)來(lái)搞（友情鏈接）三、樹形動(dòng)態(tài)規(guī)劃現(xiàn)在先拋出一道例題,體會(huì)一下樹形動(dòng)歸的思想。【題目描述】一棵樹由結(jié)點(diǎn)和與它相連

15、子樹（有 0，1或者2）組成，這些子樹被稱作兒子。 樹的描述是一系列數(shù)字，如果這個(gè)樹的兒子數(shù)是： 1、0，那么樹的描述僅僅是一列 0； 2、1，那么樹的描述是由 1開始后面跟著其兒子的描述； 3、2，那么樹的描述是由 2開始后面跟著第一個(gè)兒子的描述，然后是第二個(gè)兒子 的描述。 如圖，可用21200110來(lái)表示 樹的每個(gè)點(diǎn)都必須涂成紅、綠或者藍(lán)色，但是我們涂的時(shí)候必須遵守下面的規(guī)則： 1、結(jié)點(diǎn)和它的兒子不能有一樣的顏色， 2、如果結(jié)點(diǎn)有兩個(gè)兒子，那么它們必須有不同的顏色。 問(wèn)最多有多少個(gè)結(jié)點(diǎn)是綠色的？三、樹形動(dòng)態(tài)規(guī)劃題目的主要意思是說(shuō)，二叉樹上有邊相連的點(diǎn)顏色不能相同，所以有三種顏色求能染成綠色

16、的最大的節(jié)點(diǎn)數(shù)量。不妨分析下樣例，S=1122002010，結(jié)果是5。這就是傳說(shuō)中的三色二叉樹。我們拋開這個(gè)二叉樹的描述不管（其實(shí)這個(gè)樹的表示方法十分WS，用它來(lái)建樹十分無(wú)力）我們只分析動(dòng)歸的部分。三、樹形動(dòng)態(tài)規(guī)劃因?yàn)槲覀冎豢紤]綠色結(jié)點(diǎn)的情況，而我們也發(fā)現(xiàn)上面兩圖對(duì)于求最大值并沒(méi)有什么不同，所以我們考慮壓縮一種狀態(tài)，即每個(gè)節(jié)點(diǎn)只有兩種狀態(tài)：是綠色或不是綠色。肯定是可行的不然就不會(huì)出現(xiàn)神馬課件上了但是為什么呢，原因很簡(jiǎn)單就果斷不解釋了。拜托請(qǐng)不要說(shuō)一些廢話，Orz三、樹形動(dòng)態(tài)規(guī)劃我們考慮用一個(gè)數(shù)組fp,i來(lái)表示這個(gè)意思： p 結(jié)點(diǎn)標(biāo)號(hào) i=1 是綠色 i=0 不是綠色f數(shù)組表示各種情況下綠色節(jié)點(diǎn)

17、的最大值。于是我們得出這樣的動(dòng)歸方程：fp,1:=fleftp,0+frightp,0+1; fp,0:=maxfleftp,1+frightp,0,frightp,1+fleftp,0;它應(yīng)該有這樣的解釋：此節(jié)點(diǎn)若為綠色，則其最大值等于左兒子不是綠色的最大值加上右兒子不是綠色的的最大值加上自己；此節(jié)點(diǎn)若不是綠色，則其最大值等于左兒子是綠色右兒子不是綠色，右兒子是綠色左兒子不是綠色其中較大的一個(gè)。而對(duì)于其初始值，我們可以設(shè)每個(gè)葉子節(jié)點(diǎn)的fp,1:=1;fp,0:=0;三、樹形動(dòng)態(tài)規(guī)劃但是我們用什么順序擴(kuò)展每個(gè)節(jié)點(diǎn)呢？記得前面提到過(guò)這個(gè)問(wèn)題我們想，如果我們可以從底向上地?cái)U(kuò)展每個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的值

18、由兩個(gè)兒子來(lái)更新，就可以滿足它的無(wú)后效性。這樣我們可以從每個(gè)葉子節(jié)點(diǎn)往上做一些事情。但是，因?yàn)槲覀儫o(wú)法很容易找到葉子節(jié)點(diǎn)，所以這種方式很復(fù)雜。然而，根節(jié)點(diǎn)我們是很清楚的。所以我們可以從根節(jié)點(diǎn)先往下，找到葉子節(jié)點(diǎn)再回溯，于是我們很容易想到一種方法很顯然，根據(jù)前面說(shuō)過(guò)的遍歷順序，先遍歷兒子再遍歷根節(jié)點(diǎn)的方法顯然就是三、樹形動(dòng)態(tài)規(guī)劃所以我們就可以用下面一段代碼來(lái)搞一下：（未經(jīng)驗(yàn)證,請(qǐng)多參考注釋）procedure dp(p:longint);beginif (leftp=0) and (rightp=0) then beginfp,0:=0;fp,1:=1;exit; 如果是葉子節(jié)點(diǎn)end;dp(l

19、eftp); dp(rightp); 處理左右兒子fp,1:=fleftp,0+frightp,0+1;fp,0:=max(fleftp,1+frightp,0,frightp,1+fleftp,0); 處理根節(jié)點(diǎn)end;主過(guò)程直接調(diào)用dp(root);三、樹形動(dòng)態(tài)規(guī)劃可以在剛才的過(guò)程中看到，處理問(wèn)題時(shí)應(yīng)用了一種類似搜索的方法，不過(guò)它用一個(gè)數(shù)組記錄了計(jì)算過(guò)的值，省去了許多不必要的計(jì)算，沒(méi)錯(cuò)，這種方法就叫做記憶化搜索。這是解決樹形動(dòng)歸一種比較基本的方式。一些題外話：其實(shí)在線性動(dòng)歸的時(shí)候也可以記憶化搜索。解決動(dòng)歸有幾種常用的方法，一種就是記憶化搜索，另一種是根據(jù)某些條件直接寫出其狀態(tài)轉(zhuǎn)移的遞推式。

20、后者的效率明顯高于前者，但是在當(dāng)我們無(wú)法寫出十分簡(jiǎn)潔的遞推式的時(shí)候，暴力搜索又太慢的時(shí)候，不妨使用記憶化搜索這種比較折中的方法。你到底有沒(méi)有在說(shuō)廢話入完門，我們來(lái)討論一下去年暴虐全場(chǎng)的拾金子Orz三、樹形動(dòng)態(tài)規(guī)劃 拾金子【問(wèn)題描述：】 古老的傳說(shuō)中有一個(gè)古老的游戲，游戲的名字叫拾金子。 游戲的規(guī)則如下： 有一樹型道路，樹中每一結(jié)點(diǎn)都有一個(gè)標(biāo)號(hào)，同時(shí)有一塊標(biāo)有質(zhì)量的金子，游戲者從最上邊根結(jié)點(diǎn)出發(fā)，遍歷若干結(jié)點(diǎn)，每經(jīng)過(guò)一個(gè)結(jié)點(diǎn)都必須拿走該結(jié)點(diǎn)的金子。現(xiàn)在規(guī)定游戲者拿走的金子數(shù)目是有限的，問(wèn)怎樣走才能使得到的金子質(zhì)量最大？ (第一個(gè)數(shù)是標(biāo)號(hào)，第二個(gè)是金子重量) 具體問(wèn)題： 一棵有n個(gè)結(jié)點(diǎn)的樹（結(jié)點(diǎn)標(biāo)

21、號(hào)是1n），從中找m個(gè)點(diǎn)，使這些點(diǎn)連通并包含根結(jié)點(diǎn)，并使得所有點(diǎn)的權(quán)值（金子質(zhì)量）和最大。（如果包含10號(hào)結(jié)點(diǎn)，則必須包含9號(hào)和1號(hào)結(jié)點(diǎn)，因?yàn)榈竭_(dá)10時(shí)必須經(jīng)過(guò)9和1結(jié)點(diǎn)）Input 第一行： n, m; 以下n行；每行是：標(biāo)號(hào)父結(jié)點(diǎn)金子質(zhì)量 Output 得到的最大和。三、樹形動(dòng)態(tài)規(guī)劃Sample Input 10 52 9 91 9 14 2 15 2 19 0 16 9 110 1 203 2 18 6 67 6 4Sample Output 32數(shù)據(jù)規(guī)模：40% 1=n=10 100% 1=n=100 1=m=n 1=金子重量=1000三、樹形動(dòng)態(tài)規(guī)劃這是樣例的解釋圖。我們思考一下的話

22、可以設(shè)立這樣一個(gè)數(shù)組fp,k即在p下選取k個(gè)節(jié)點(diǎn)獲得的最大收益。直接在樹上做也可，但是每個(gè)點(diǎn)的度都不同，我們需要特別開一個(gè)數(shù)組來(lái)紀(jì)錄每個(gè)點(diǎn)的度以及兒子下標(biāo)，使問(wèn)題比較復(fù)雜，而且空間也要開很大。于是我們想到把樹改造下，改成二叉樹是最好不過(guò)的了。于是就用左兒子右兄弟改造一翻再思考一些狀態(tài)轉(zhuǎn)移三、樹形動(dòng)態(tài)規(guī)劃我們思考動(dòng)態(tài)轉(zhuǎn)移方程。fp,k表示在這個(gè)節(jié)點(diǎn)中選k個(gè)節(jié)點(diǎn)的最大值，那么如果選這個(gè)節(jié)點(diǎn)，那么還可以在它的左兒子里選i=0k-1個(gè)節(jié)點(diǎn)，對(duì)應(yīng)的在它的右兄弟里選k-1-i個(gè)節(jié)點(diǎn)。如果不選這個(gè)節(jié)點(diǎn)，那么它兒子的節(jié)點(diǎn)都不能選，只能從它的右兄弟里選k個(gè)。所以我們得到這個(gè)狀態(tài)轉(zhuǎn)移方程：fp,k:=fright

23、p,k;fp,k:=maxfleftp,i+ap+frightp,k-1-i i=0k-1fp,k取上面兩者的最大值。為了使問(wèn)題更加簡(jiǎn)化，我們可以直接把frightp,k賦為它的初始值。而對(duì)于初始值，可以把每個(gè)節(jié)點(diǎn)取0個(gè)節(jié)點(diǎn)的值賦為0，把不存在的節(jié)點(diǎn)的值賦為零。于是我們將見到本課件中差不多是第三段代碼。來(lái)插一下屏.Kudo：你到你是什么人三、樹形動(dòng)態(tài)規(guī)劃procedure dp(p,k:longint);beginif p=0 then begin fp,k:=0; exit; end; 邊界條件if k=0 then begin fp,k:=0; exit; end;dp(rightp,k)

24、;ans:=frightp,k; 不選節(jié)點(diǎn)p從右兄弟選k個(gè)for i:=0 to k-1 do 選節(jié)點(diǎn)p的情況begindp(leftp,i);dp(rightp,k-i-1);ans:=max(ans,fleftp,i+ap+frightp,k-i-1;end;fp,k:=ans;end;再加上左兒子右兄弟的轉(zhuǎn)換，我們就完成了對(duì)此題的求解。三、樹形動(dòng)態(tài)規(guī)劃我們?cè)賮?lái)看今天的最后一題！ TYVJP1052沒(méi)有上司的舞會(huì) Ural大學(xué)有N個(gè)職員，編號(hào)為1N。他們有從屬關(guān)系，也就是說(shuō)他們的關(guān)系就像一棵以校長(zhǎng)為根的樹，父結(jié)點(diǎn)就是子結(jié)點(diǎn)的直接上司。每個(gè)職員有一個(gè)快樂(lè)指數(shù)?，F(xiàn)在有個(gè)周年慶宴會(huì)，要求與會(huì)職員

25、的快樂(lè)指數(shù)最大。但是，沒(méi)有職員愿和直接上司一起與會(huì)。輸入格式 Input Format 第一行一個(gè)整數(shù)N。(1=N=6000) 接下來(lái)N行，第i+1行表示i號(hào)職員的快樂(lè)指數(shù)Ri。(-128=Ri=127) 接下來(lái)N-1行，每行輸入一對(duì)整數(shù)L,K。表示K是L的直接上司。 最后一行輸入0,0。輸出格式 Output Format 輸出最大的快樂(lè)指數(shù)。三、樹形動(dòng)態(tài)規(guī)劃輸入樣例:711111111 32 36 47 44 53 50 0輸出樣例：5三、樹形動(dòng)態(tài)規(guī)劃樹上的DP比較容易想，所以我們先考慮在樹上的。（就是說(shuō)先不轉(zhuǎn)二叉樹）簡(jiǎn)述題意：樹上的每個(gè)點(diǎn)都有其權(quán)值，對(duì)每一個(gè)點(diǎn)，選了這個(gè)點(diǎn)就不能選它的兒子

26、，求能得到的最大的權(quán)值。三、樹形動(dòng)態(tài)規(guī)劃設(shè)數(shù)組fp,0表示選這個(gè)點(diǎn)，fp,1表示不選這個(gè)點(diǎn)。初始化fp,0=0 fp,1=ap（ap即為其價(jià)值）對(duì)于每個(gè)點(diǎn)fp,1:=max(fp,1,fp,1+fz,0);fp,0:=max(fp,0,fp,0+x);x:=max(fz,1,fz,0); （z取p的所有兒子）這種方法可以154ms AC但是，這種方法有一個(gè)明顯的bug不要這么打擊wo三、樹形動(dòng)態(tài)規(guī)劃這個(gè)bug就是內(nèi)存這樣做的話必須要開這樣兩個(gè)數(shù)組，就像是鄰接表的存儲(chǔ)v1.6000 表示每個(gè)點(diǎn)有多少兒子g1.6000,1.6000 表示每個(gè)兒子的下標(biāo)而后面那個(gè)數(shù)組明顯要爆的，抱著鄙視數(shù)據(jù)的心態(tài)，我開了g1.6000,1.5