樹(shù)形動(dòng)規(guī)初探-葉詩(shī)富

1、四川省綿陽(yáng)南山中學(xué)葉詩(shī)富電話(huà)Q：282364860內(nèi)容簡(jiǎn)介本文以一些常見(jiàn)題目為載體，由淺入深介紹樹(shù)形動(dòng)規(guī)的一般處理方法和技巧，學(xué)習(xí)樹(shù)形動(dòng)規(guī)的常見(jiàn)模型以及相關(guān)的綜合應(yīng)用。樹(shù)是一種十分優(yōu)美的數(shù)據(jù)結(jié)構(gòu)，因?yàn)樗旧砭途哂械倪f歸性，所以樹(shù)和子樹(shù)之間能相互傳遞很多信息，樹(shù)上的許多特征都可以通過(guò)它的子樹(shù)的對(duì)應(yīng)特征計(jì)算獲得。所以樹(shù)做動(dòng)態(tài)規(guī)劃求最優(yōu)解和做統(tǒng)計(jì)非常方便。12563412563478認(rèn)識(shí)樹(shù)125634樹(shù)上最長(zhǎng)鏈給定一棵樹(shù)，樹(shù)上共有N個(gè)節(jié)點(diǎn)(N=5000) ，樹(shù)上節(jié)點(diǎn)的編號(hào)從1到N，每個(gè)節(jié)點(diǎn)的兒子個(gè)數(shù)最多為N-1，請(qǐng)求出這棵樹(shù)上的經(jīng)過(guò)節(jié)點(diǎn)數(shù)最多的一條不重復(fù)的鏈。輸入：第一行一

2、個(gè)數(shù)N，表示樹(shù)有N個(gè)節(jié)點(diǎn)。接下來(lái)N行，每行第一個(gè)數(shù)為Xi(0=Xi=N-1),表示編號(hào)為i的節(jié)點(diǎn)的兒子個(gè)數(shù)為Xi,接下來(lái)Xi個(gè)數(shù)，依次表示每一個(gè)兒子的編號(hào)。Xi為0表示沒(méi)有兒子。輸出：一行一個(gè)數(shù)，表示最長(zhǎng)鏈經(jīng)過(guò)的節(jié)點(diǎn)個(gè)數(shù)。（內(nèi)存限制10M）目標(biāo)：如圖計(jì)算1為根的樹(shù)上最長(zhǎng)鏈動(dòng)機(jī)：通過(guò)分析子樹(shù)的相關(guān)信息，算出目標(biāo)值有兩種情況：一、最長(zhǎng)鏈不經(jīng)過(guò)1號(hào)節(jié)點(diǎn).二、最長(zhǎng)鏈經(jīng)過(guò)1號(hào)節(jié)點(diǎn)。問(wèn)題分析12563478狀態(tài)定義：fi表示以i為根的樹(shù)上從i點(diǎn)向下能得到的最長(zhǎng)鏈。fi=max(fson+Wi,son ),W表示i點(diǎn)到它對(duì)應(yīng)兒子的邊長(zhǎng)DPi表示以i為根的樹(shù)的最長(zhǎng)鏈(包括過(guò)節(jié)點(diǎn)i和不過(guò)節(jié)點(diǎn)i的最長(zhǎng)鏈)DPi=

3、max(DPson,max(fson1+fson2+Wison1+Wison2)此題還有兩個(gè)困難。1.樹(shù)的根沒(méi)有明確給出。沒(méi)有根我們不能方便的在樹(shù)上做動(dòng)規(guī)2每個(gè)節(jié)點(diǎn)的最大兒子個(gè)數(shù)不確定。保存樹(shù)有一定的麻煩問(wèn)題分析問(wèn)題一解決比較簡(jiǎn)單我們掃描數(shù)據(jù)，根節(jié)點(diǎn)不是任何一個(gè)節(jié)點(diǎn)的兒子，就可以找出根節(jié)點(diǎn)來(lái)。對(duì)于問(wèn)題二的解決。因?yàn)檎鎸?shí)的父子關(guān)系只有N-1個(gè)，我們只需開(kāi)N個(gè)空間就可以保存信息，只是我們需另外開(kāi)兩個(gè)大小為N的數(shù)組，來(lái)記錄每個(gè)節(jié)點(diǎn)的兒子個(gè)數(shù)和開(kāi)始位。問(wèn)題求解此題的輸入有特殊性，存儲(chǔ)問(wèn)題好解決。但對(duì)于大多數(shù)的題目，信息是以邊的形式給的且是無(wú)序的。常用鄰接表保存(這也是一般圖的存儲(chǔ)方法)。大致處理方法如

4、下：用一個(gè)大小為2倍N的鏈表來(lái)記錄樹(shù)上各邊的信息，具有相同頂點(diǎn)的邊串在一起，再用一個(gè)大小為N的數(shù)組作為表頭，記錄每一個(gè)點(diǎn)連出的鏈表開(kāi)頭的位置。這樣我們就可以通過(guò)表頭訪(fǎng)問(wèn)節(jié)點(diǎn)出去的每個(gè)點(diǎn)了。方法拓展方法拓展存樹(shù)代碼：int headN,cnt_li;struct LI int la,v; liN1;void add(int a,int b) li+cnt_li = (LI)heada,b; heada = cnt_li;0350256347表頭鏈表12360000123456下標(biāo)下標(biāo)4567沒(méi)有上司的晚會(huì)沒(méi)有上司的晚會(huì)Ural1039加強(qiáng)加強(qiáng) 公司的人際關(guān)系構(gòu)成一棵樹(shù)，現(xiàn)公司要舉行一場(chǎng)晚會(huì)并規(guī)定

5、：如果邀請(qǐng)了某個(gè)人，那么一定不會(huì)邀請(qǐng)他的上司（上司的上司，上司的上司的上司都可以邀請(qǐng)）。每個(gè)人都有一個(gè)氣氛值，求一個(gè)邀請(qǐng)方案，使氣氛值的和最大。數(shù)據(jù)規(guī)模： N表示公司的人數(shù)。（1=N=100000）12563478因公司的人際關(guān)系為一棵樹(shù)，假設(shè)編號(hào)為root的節(jié)點(diǎn)是樹(shù)的根，則問(wèn)題可以描述成froot表示求以root為根的樹(shù)上能得到的最大氣氛和。我們希望用root的兒子的對(duì)應(yīng)信息來(lái)推出froot.由于節(jié)點(diǎn)root 有選和不選兩種可能，所以當(dāng)我們r(jià)oot節(jié)點(diǎn)選擇時(shí)，需要它的子節(jié)點(diǎn)不選時(shí)的最大值，當(dāng)root節(jié)點(diǎn)不選時(shí)，它的子節(jié)點(diǎn)選和不選都可以。所以我們需要加半維來(lái)表示樹(shù)的根結(jié)點(diǎn)是否選取才能從子樹(shù)推算

6、出父親的最大值。問(wèn)題分析定義狀態(tài)fi,j表示以i為根的樹(shù)能得到的最大的氣氛和，j=0時(shí)表示根節(jié)點(diǎn)不選，j=1時(shí)表示根節(jié)點(diǎn)要選。狀態(tài)轉(zhuǎn)移方程為Fi,0=max(fson,1,fson,0);其中son為i的子節(jié)點(diǎn)。Fi,1= fson,0+gi;其中g(shù)i表示節(jié)點(diǎn)i的氣氛值。答案是max(froot,0,froot,1) root為整棵樹(shù)的根。時(shí)間復(fù)雜度為O（N）空間復(fù)雜度為O（N）問(wèn)題求解int DP(int a,int b)if(usedab!=inf) return usedab;usedab=0;int ans=0;for(int i=heada;i;i=fi.next)int t=DP(

7、fi.go,0);if(b=0) t=max(t,DP(fi.go,1);ans+=t;ans+=b*da;usedab=ans; return ans;參考代碼根據(jù)上面的分析，利用樹(shù)的遞歸性，通過(guò)子樹(shù)的對(duì)應(yīng)信息，推出了樹(shù)上想要的信息，從而找出了問(wèn)題的解。問(wèn)題拓展問(wèn)題好像已經(jīng)完美解決。但我們會(huì)發(fā)現(xiàn)還有一些數(shù)據(jù)會(huì)出錯(cuò)。注意到N的大小為10萬(wàn)，用遞歸實(shí)現(xiàn)記憶化搜索，極端數(shù)據(jù)會(huì)產(chǎn)生棧溢出錯(cuò)誤 。有兩種比較常用的辦法可以解決這個(gè)問(wèn)題。void solve() queueq; q.push(root); int now,p=0; while (!q.empty() now=q.front();q.pop

8、();s+p=now; for (int i=headnow;i;i=nexi) q.push(toi); for (int i=p;i=1;-i) now=si; for(int j=headnow;j;j=nxtj) fnow0+=max(ftoj0,ftoj1); for(int j=headnow;j;j=nxtj) fnow1+=ftoj0; fnow1+=valnow; 方法一采用廣搜實(shí)現(xiàn)，擴(kuò)展每一個(gè)節(jié)點(diǎn)，將沒(méi)搜過(guò)的兒子節(jié)點(diǎn)加入隊(duì)列，廣搜結(jié)束后反向刷新（用兒子節(jié)點(diǎn)的值去刷父親節(jié)點(diǎn)）搜索隊(duì)列中的值即可。深搜的非遞歸實(shí)現(xiàn)方法如下：擴(kuò)展每個(gè)節(jié)點(diǎn)，將當(dāng)前兒子節(jié)點(diǎn)加入棧并處理，直到其所有兒子

9、節(jié)點(diǎn)都已經(jīng)被處理，就更新其父親節(jié)點(diǎn)并將其彈出棧。方法二參考代碼：void DP(int a) S.push(a);memcpy(head2,head,sizeof(head);while (!S.empty() int a=S.top(); useda=true; if (head2a)/還有兒子沒(méi)走 int tal=fhead2a.go; if (!usedtal) S.push(tal); /兒子未被訪(fǎng)問(wèn)過(guò) head2a=fhead2a.next; continue; /兒子節(jié)點(diǎn)已處理完 ansa1+=vala; ansfaa0=max(ansfaa0,max(ansa0,ansa1);

10、/更新父節(jié)點(diǎn) ansfaa1=max(ansfaa1,ansa0); S.pop();/彈出該點(diǎn)二叉蘋(píng)果樹(shù)二叉蘋(píng)果樹(shù) 有一棵蘋(píng)果樹(shù)，它是一棵二叉樹(shù)，共N個(gè)節(jié)點(diǎn)，樹(shù)節(jié)點(diǎn)編號(hào)為1N，編號(hào)為1的節(jié)點(diǎn)為樹(shù)的根，邊可理解為樹(shù)的分枝，每個(gè)分支都長(zhǎng)著若干個(gè)蘋(píng)果，現(xiàn)在要減去若干個(gè)分支，保留M個(gè)分支，使得這M個(gè)分支中的蘋(píng)果數(shù)量最多。1256347810352345問(wèn)題分析此題和前面的題有個(gè)明顯不同的地方，我們關(guān)注樹(shù)的信息，還需要在樹(shù)上分配資源。所以我們描述問(wèn)題時(shí)需增加一維表示要分配的資源,用fi,j表示以i為根的樹(shù)上保留j個(gè)邊能獲得的最多的蘋(píng)果個(gè)數(shù)。我們可以用子樹(shù)的相關(guān)特性算出樹(shù)的相關(guān)特性。fi,j=max(f

11、sonl,j-1+Wi,sonl,fsonr,j-1+Wi,sonr,fsonl，j+fsonr,j-2-j+ Wi,sonl+Wi,sonr),0=j=1; j-) for(int k=1 ; kj ; k+) dpuj = max(dpuj , dpvk + dpuj-k + ei.d); 有限電視網(wǎng)絡(luò)(pku1155)有一棵N個(gè)節(jié)點(diǎn)的樹(shù)，樹(shù)上有M個(gè)葉子節(jié)點(diǎn)，對(duì)應(yīng)M個(gè)用戶(hù)，其余為轉(zhuǎn)發(fā)站，1號(hào)節(jié)點(diǎn)為根，電視臺(tái)在1號(hào)節(jié)點(diǎn)，節(jié)目從一個(gè)地方傳到另一個(gè)地方都要費(fèi)用，同時(shí)每一個(gè)用戶(hù)愿意出相應(yīng)的錢(qián)來(lái)收看節(jié)目。求在電視臺(tái)不虧本的前提下，最多允許有多少個(gè)用戶(hù)可以看到電視節(jié)目。規(guī)模：N=3000 MN12 3

12、674859問(wèn)題分析困難一 題目求最多的用戶(hù)數(shù)，同時(shí)也需分配資源，所以借鑒上題的經(jīng)驗(yàn)我們得到如下?tīng)顟B(tài)描述：Fi,j表示在以i為根的樹(shù)上用j元，能允許的最多用戶(hù)數(shù)。行嗎？考慮到用戶(hù)數(shù)最多是M，所以可以換一種定義方法。Fi,j表示以i為根的樹(shù)允許j個(gè)用戶(hù)的最大收益。這樣狀態(tài)數(shù)就變成了N*M.問(wèn)題分析困難二此題與上題還有一個(gè)不同，就是樹(shù)是一棵多叉樹(shù)。這樣轉(zhuǎn)移的時(shí)候就有需要考慮的地方，由于樹(shù)的兒子較多，我們需要枚舉每一個(gè)兒子分配多少資源。搜出所有方案再來(lái)算效率非常低。123674859注意到我們可以先做一次DP獲得只看子樹(shù)時(shí)對(duì)應(yīng)的最優(yōu)值，然后再在樹(shù)上DP即可。兩次DP。具體理解，可看下圖。 DPij表

13、示以i為根的樹(shù)選j個(gè)用戶(hù)的最大獲利。對(duì)于每棵子樹(shù)形成的兒子序列，我們?cè)谛蛄猩献鲆淮伪嘲?。fij = max(fi-1j,DPi對(duì)應(yīng)樹(shù)上的節(jié)點(diǎn)j + fi-1j-j -len);(1=j=1，需要枚舉，k為i的子節(jié)點(diǎn)，需要枚舉,len為邊權(quán))編程實(shí)現(xiàn)的技巧：所有節(jié)點(diǎn)向父節(jié)點(diǎn)建有向邊，按照拓?fù)湫虻捻樞蜻M(jìn)行dp時(shí)間復(fù)雜度：O(n * m * m) 空間復(fù)雜度：O(n * m)問(wèn)題求解 void dfs(int u,int father) int i,j,k,v; for(j=headu;j!=-1;j=edgej.next) v=edgej.to; if(v=father) continue; df

14、s(v,u); sumu+=sumv; for(i=sumu;i=1;i-) /sumu表示已枚舉到的u下面葉子節(jié)點(diǎn)的個(gè)數(shù)，一定要倒序枚舉 for(k=1;k=sumv & k=i;k+) /sumv表示v下面葉子節(jié)點(diǎn)的個(gè)數(shù) DPui=Max(DPui,DPvk+DPui-k-edgej.val); 參考代碼很郁悶的金明 給出N個(gè)物品，可以直接被購(gòu)買(mǎi)的稱(chēng)為主件，而不能直接被購(gòu)買(mǎi)的稱(chēng)為附件，附件只有當(dāng)其主件被購(gòu)買(mǎi)了才能被購(gòu)買(mǎi)，一個(gè)主件可以有任意多個(gè)附件，附件可以有多級(jí)，每個(gè)物品都有一個(gè)權(quán)值(50000)。任務(wù)購(gòu)買(mǎi)一些物品，總價(jià)格不超過(guò)M，使得被購(gòu)買(mǎi)的物品的權(quán)值之和最大。N60,M3200

15、0 定義：f(i,j)表示以i為根的樹(shù)花j元能獲得的最大權(quán)值和。轉(zhuǎn)移和上面類(lèi)似，轉(zhuǎn)移太麻煩問(wèn)題分析 利用樹(shù)的先根或后根遍歷，將樹(shù)線(xiàn)性化。樹(shù)上的背包問(wèn)題轉(zhuǎn)化成了我們熟悉的線(xiàn)性背包問(wèn)題了，以后根遍歷為例。問(wèn)題分析1236748596 7 2 3 8 4 9 5 1后根遍歷得到序列 定義狀態(tài)fi,j表示前i個(gè)點(diǎn)用j元，能獲得的最大權(quán)值和。轉(zhuǎn)移:fi,j=max(fi,j,fi-1,j-vi+Wi) (i為離子樹(shù)i最近的一個(gè)節(jié)點(diǎn))復(fù)雜度為O(N*M)。如何計(jì)算i？只需在線(xiàn)性化時(shí)遞歸時(shí)記下當(dāng)前是位置減1即可。問(wèn)題分析 此題成功將樹(shù)上的DP轉(zhuǎn)化成一個(gè)線(xiàn)形的Dp,并且復(fù)雜度還優(yōu)化了一維下來(lái)。思考上面兩個(gè)題目

16、可否用相同的思路優(yōu)化一下？問(wèn)題拓展答案是肯定的。二叉蘋(píng)果樹(shù)的狀態(tài)fij表示前i個(gè)結(jié)點(diǎn)保留j個(gè)分支能收獲的最多蘋(píng)果數(shù)有線(xiàn)電視網(wǎng)的狀態(tài)定義fij前i個(gè)結(jié)點(diǎn)中選j個(gè)用戶(hù)的最大收益。貪吃的九頭龍NOI2002有M個(gè)腦袋的九頭龍要吃掉N個(gè)果子，它需要把N個(gè)果子分成M組，每組至少有一個(gè)果子，讓每個(gè)頭吃一組。 其中最大的頭要吃掉恰好K個(gè)果子，且包括第一個(gè)果子。果子構(gòu)成一棵樹(shù)。對(duì)于每段樹(shù)枝的兩個(gè)果子需要由不同的頭來(lái)吃則沒(méi)有難受值，否則有一個(gè)難受值。求最小的“難受值”之和。N(1=N=300)，M(2=M=N)，K(1=K=N)。圖和樣例說(shuō)明12435678201012154135124356782010121

17、54135頭的個(gè)數(shù)與向上傳遞信息的算法有關(guān)。兩種情況：頭個(gè)數(shù)大于2，小頭需要吃的果子，可由兩個(gè)小頭共同完成，所以只考慮大頭的情況。頭個(gè)數(shù)等于2，既要考慮大頭的難受值，又要考慮小頭的難受值。fi,j表示以i為根的樹(shù)，大頭吃j個(gè)果實(shí)的最小難受值。轉(zhuǎn)移時(shí)需要知道它的子樹(shù)的根是否是大頭所吃。所以增加半維。定義狀態(tài)fi,j,k表示以i為根的樹(shù)，大頭吃j個(gè)果子的最小難受值。K=0表示大頭不吃根節(jié)點(diǎn)，K=1表示大頭吃根節(jié)點(diǎn)。問(wèn)題分析 轉(zhuǎn)移方程為：(v是i的一個(gè)兒子, temp為上一次轉(zhuǎn)移完后的f值,wij為(i,j)這條邊的難受值)fij1=min fvk1+tempij-k1+wiv, fvk0+temp

18、ij-k1 ;(0=kj)fij0=min fvk1+tempij-k0, fvk0+tempij-k0+wiv (m=2) fvk0+tempij-k0 (m2) ;(0=k2) flk0+frj-k0+Wi (M=2) ;COCI(2008)- PERIODNI給定一個(gè)N列的表格，每列的高度各不相同，但底部對(duì)齊，然后向表格中填入K個(gè)相同的數(shù)，填寫(xiě)時(shí)要求不能有兩個(gè)數(shù)在同一列，或同一行，下圖中b是錯(cuò)誤的填寫(xiě)，a是正確的填寫(xiě)，因?yàn)閮蓚€(gè)a雖然在同一行，但它們中間的表格斷開(kāi)。 輸出所有填寫(xiě)方案數(shù)對(duì)1 000 000 007的余數(shù)。輸入：第一行兩個(gè)整數(shù) N 和 K (1 N 500, 1 K 500)

19、,表示表格的列數(shù)和要填寫(xiě)的數(shù)的個(gè)數(shù)。接下來(lái)一行N個(gè)數(shù)，表示每列的高度。高度不超過(guò) 1 000 000.輸出：一個(gè)整數(shù)，方案總數(shù)對(duì)1000 000 007的余數(shù)。注意：對(duì)于 40% 的數(shù)據(jù), 所有數(shù)值小于15.對(duì)于70% 的數(shù)據(jù)，所有數(shù)值小于100.baab問(wèn)題分析問(wèn)題分析12536478910轉(zhuǎn)成樹(shù)的方法和代價(jià) 程序?qū)崿F(xiàn)時(shí)，由于列數(shù)N較小，可以采用直接掃描，找出最小值，然后拆分建樹(shù)，時(shí)間復(fù)雜度為O(N2), 當(dāng)然我們最好采用增加空節(jié)點(diǎn)的辦法，讓樹(shù)最多二叉,以方便后面動(dòng)規(guī)。由于每建立一個(gè)節(jié)點(diǎn)，都會(huì)將規(guī)模至少減小一列，所以我們需要建的節(jié)點(diǎn)總數(shù)也不超過(guò)N問(wèn)題求解 在樹(shù)上定義狀態(tài) fi,j表示以i為根

20、的樹(shù)上放j個(gè)字符的方案總數(shù)。 gi,j表示以i為根的樹(shù)左右兒子共填j個(gè)字符的方案總數(shù)。 ha,b,k表示底邊長(zhǎng)為a，高為b的矩形中放k個(gè)字符的方案總數(shù)。 狀態(tài)轉(zhuǎn)移： fi,j=(hia-j,ib,j-j*gi,j)(0=j=j). gi,j= (fson左,j*fson右,j-j)(0=j=j). 狀態(tài)總數(shù)是N*K，轉(zhuǎn)移是K，所以總的復(fù)雜度是O(N*K*K)由于b 特別大我們沒(méi)有直接預(yù)先處理出h，只能需要時(shí)計(jì)算，可以先預(yù)處理出階乘取模的值，以及階乘對(duì)mod值的逆元。參考代碼void dfs(int x)/hi表示節(jié)點(diǎn)所代表矩形的高度，width表示節(jié)點(diǎn)所代表矩形的長(zhǎng)度。 if (!x) ret

21、urn ; dfs(sonx0);dfs(sonx1); for (int i=0;i=K;+i) for (int j=0;j=i;+j) gxi += fsonx0j*fsonx1i-j;/預(yù)處理g數(shù)組 for (int i=0;i=K;+i) for (int j=0;j=i;+j) fxi += gxj*calc(widthx-j,hix,i-j); /calc(i,j,k) 表示長(zhǎng)為i，高為j的矩形中填k個(gè)數(shù)的方案數(shù)所駝門(mén)王的寶藏所駝門(mén)王的寶藏給定一個(gè)R*C的矩陣迷宮，每個(gè)格子是一個(gè)房間，房間與外界、房間與房間均不能相互通過(guò)。有N個(gè)房間里有寶藏和傳送門(mén)，傳送門(mén)分為三種，一是同行傳送，

22、二是同列傳送，三是相鄰的八個(gè)格子傳送。你有一次機(jī)會(huì)通過(guò)外部傳送門(mén)，進(jìn)入迷宮并出來(lái)，問(wèn)能得到的的最多的寶藏？N=100000,R,C=1000000題目求解把房間看成點(diǎn)，房間A能到房間B，則有A向B建一條有向邊，最后會(huì)形成一個(gè)有向圖。圖中在同一強(qiáng)連通分量中的點(diǎn)，肯定會(huì)同時(shí)選取，所以可以將強(qiáng)連通分量縮點(diǎn)，形成有向樹(shù)或森林，問(wèn)題變成了在樹(shù)上找一個(gè)點(diǎn)出發(fā)，能得到的最大收益。我們?cè)跇?shù)上做一次DP即可。由于R、C都很大，建圖時(shí)，一行或一列的傳送門(mén)同種類(lèi)型的點(diǎn)之間都向第一個(gè)點(diǎn)建雙向邊，第一個(gè)點(diǎn)向其它類(lèi)型的點(diǎn)建邊。給出一個(gè)凸多邊形的三角剖分(n=100000)，求每條對(duì)角線(xiàn)穿過(guò)的三角形個(gè)數(shù)，輸出最大值。三角形

23、剖分12345671234567三角形看成點(diǎn)枚舉所有對(duì)角線(xiàn)，再判斷這條對(duì)角線(xiàn)穿過(guò)多少三角形，復(fù)雜度太高N312435問(wèn)題分析有公共邊的三角形連線(xiàn)構(gòu)成一棵樹(shù)，為什么是樹(shù)？考慮刪除一個(gè)三角形，凸多邊形被分成了完全獨(dú)立的部分，因此任意兩個(gè)三角形之間只有一條唯一的路徑，構(gòu)成一棵樹(shù)。問(wèn)題分析 對(duì)于凸多邊形，一條對(duì)角線(xiàn)，對(duì)應(yīng)樹(shù)上的一條路徑。 一條路徑對(duì)應(yīng)唯一的對(duì)角線(xiàn)。123456712435問(wèn)題求解問(wèn)題轉(zhuǎn)化成求所有葉子節(jié)點(diǎn)間的最遠(yuǎn)距離也就是轉(zhuǎn)化成例一的問(wèn)題。時(shí)間復(fù)雜度 O(n)注意棧溢出！迷失游樂(lè)園（NOI2012）給定一個(gè)n點(diǎn)、m條邊的無(wú)向連通圖。小Z隨機(jī)從某個(gè)點(diǎn)出發(fā)，每次隨機(jī)等概率地去一個(gè)和當(dāng)前點(diǎn)有邊

24、的點(diǎn)，并且同一個(gè)點(diǎn)不去兩次（包括起始點(diǎn)）。這個(gè)過(guò)程一直進(jìn)行，直到當(dāng)前點(diǎn)的所有相鄰點(diǎn)都已經(jīng)訪(fǎng)問(wèn)過(guò)為止。小Z所有經(jīng)過(guò)的點(diǎn)按順序構(gòu)成一條非重復(fù)路徑，他想知道這條路徑的期望長(zhǎng)度是多少？數(shù)據(jù)規(guī)模：對(duì)50%的數(shù)據(jù) ：m=n-1;另外50%的數(shù)據(jù)，m=n,且環(huán)上點(diǎn)數(shù)不超過(guò)20;100%的數(shù)據(jù)有n4 81/42-131/82-451/83-141/83-441/84-181/4共有6條不同的路徑: 首先考慮前50分是樹(shù)的情況由樹(shù)型DP的經(jīng)驗(yàn)，我們可以定義一個(gè)狀態(tài)f(i)表示以i為根的樹(shù)，i點(diǎn)出發(fā)的路徑的期望長(zhǎng)度。我們嘗試用子樹(shù)的相關(guān)信息來(lái)得到原問(wèn)題的解。 則有 (w(i,j)表示i到j(luò)的邊權(quán)，sizei是i的

25、兒子個(gè)數(shù)，j是i的兒子。)這樣我們求出了根結(jié)點(diǎn)的路徑期望長(zhǎng)度。問(wèn)題分析)()(),()(isizejfjiwif題目要求每個(gè)點(diǎn)出發(fā)的路徑期望長(zhǎng)度之和，其它節(jié)點(diǎn)出發(fā)的期望長(zhǎng)度怎么算？簡(jiǎn)單的方法是以每個(gè)點(diǎn)為根，求一下期望長(zhǎng)度。但這樣的復(fù)雜度較高，為N*N。 考慮繼承一下上一次的計(jì)算結(jié)果，我們記下f(i,fa)表示以i為根，父節(jié)點(diǎn)為fa時(shí)樹(shù)的期望長(zhǎng)度。這樣記下的樹(shù)的形態(tài)不會(huì)改變，算過(guò)的就不會(huì)再算了。感覺(jué)狀態(tài)從一維變成二維了，轉(zhuǎn)移沒(méi)有變，其實(shí)狀態(tài)只有2*N，因?yàn)閒定義中的父子，實(shí)際對(duì)應(yīng)的是邊。所以狀態(tài)是邊數(shù)乘以2。由于記下了算過(guò)的東西，所以表現(xiàn)較好，復(fù)雜度接近線(xiàn)N。但對(duì)于扇形的數(shù)據(jù)，它的復(fù)雜度是N*N

26、的。問(wèn)題求解一我們?cè)诿杜e計(jì)算以1、2、3、5、6為根的樹(shù)時(shí)都會(huì)算到以4為根1為父親這棵樹(shù)12563478 還有一種方法是考慮根節(jié)點(diǎn)和它相鄰節(jié)點(diǎn)的微小差異，從1號(hào)節(jié)點(diǎn)為根的值推出與之相連的節(jié)點(diǎn)為根的期望值。問(wèn)題求解二1256347812563478) 1) 1 (/()4 , 1 ()4() 1 () 1 () 1 ( sizewfsizeff 1)4(/)1 , 4() 1 ( )4()4()4( sizewfsizeff void dfs(int u) for(int i=headu;i;i=edgei.next) int v=edgei.v; if(fau!=v&!incv) si

27、zeu+; wv=edgei.w; fav=u; brov=sonu; sonu=v; dfs(v); for(int v=sonu;v;v=brov)fu+=fv+wv; if(sizeu)fu=fu/sizeu;注意：分母為零需特殊處理參考代碼：先求出所有的down(i)(表示以i為根的樹(shù)向下的期望值),up(i)：先向上移動(dòng)至fa(i)后的期望值(下一步可訪(fǎng)問(wèn)fa(i)的父親或i的兄弟)。問(wèn)題求解三)()()()()()(fasizeidownwfasizefadownfaupwiup)()()()(fasizewidownfaupfadownw其中fa為i的父親，w為連結(jié)fa與i的邊的

28、權(quán)值。iifaibroW 第二種情況，我們發(fā)現(xiàn)由于環(huán)的大小很小(環(huán)上最多20個(gè)點(diǎn))，所以我們可以暴力枚舉路徑進(jìn)入環(huán)的一點(diǎn)和走出環(huán)的一點(diǎn)，這樣我們可以將環(huán)移除，問(wèn)題退化為樹(shù)的情況。這時(shí)使用前一種情況的方法就可以解決了。 對(duì)于有一個(gè)環(huán)的情況，可以分兩種情況討論：第一種情況，我們可以繼續(xù)使用之前所說(shuō)的樹(shù)型DP問(wèn)題分析the lost house 蝸牛的房子遺失在一棵樹(shù)的某個(gè)葉子結(jié)點(diǎn)上，它要從根結(jié)點(diǎn)出發(fā)開(kāi)始尋找它的房子。有一些中間結(jié)點(diǎn)可能會(huì)住著一些蟲(chóng)子，這些蟲(chóng)子會(huì)告訴蝸牛它的房子是否在以這個(gè)結(jié)點(diǎn)為根的子樹(shù)上，這樣蝸牛就不用白跑路了。當(dāng)然，如果有些結(jié)點(diǎn)沒(méi)有住著蟲(chóng)子的話(huà)，那么蝸牛只有靠自己決定訪(fǎng)問(wèn)順序來(lái)尋

29、找了。蝸牛走過(guò)一條邊的花費(fèi)是1，且房子遺失在每個(gè)葉子結(jié)點(diǎn)的概率都是相等的，求蝸牛找到它的房子的最小數(shù)學(xué)期望值？ 樹(shù)上的結(jié)點(diǎn)數(shù)n=1000，每個(gè)結(jié)點(diǎn)的兒子結(jié)點(diǎn)數(shù)k=8。 32145蝸牛訪(fǎng)問(wèn)順序2、3、(4或5)，則走到葉子節(jié)點(diǎn)2、4、5的步數(shù)分別是1、4、6。期望值是(1+4+6)/3=11/3。蝸牛訪(fǎng)問(wèn)順序3、(4或5)、2，則走到葉子節(jié)點(diǎn)2、4、5步數(shù)分別是3、2、4。期望值是(3+2+4)/3=3。題目分析fx1表示房子在x結(jié)點(diǎn)為根的子樹(shù)上的路徑長(zhǎng)度和fx0表示房子不在x結(jié)點(diǎn)為根的子樹(shù)上的路徑長(zhǎng)度和sx表示x結(jié)點(diǎn)為根的子樹(shù)的葉子結(jié)點(diǎn)的個(gè)數(shù)。 用r1,r2.rk表示x的兒子,用每個(gè)兒子按輪刷

30、新： fx1=fx1+(fx0+1)*sri+fri1;fx0=fx0+fri0+2;對(duì)于兒子結(jié)點(diǎn)選擇的順序不同，其答案也不一樣。 一種比較樸素的方法就是k！的枚舉訪(fǎng)問(wèn)順序. k=8時(shí)，復(fù)雜度O(n*k!)，但還可以?xún)?yōu)化。問(wèn)題求解假設(shè)r1,r2為x的兒子結(jié)點(diǎn)且選擇順序相鄰，t為當(dāng)前的fx1。 如果r1的選擇順序在r2之前： =t+(fx0+1)*sr1+fr11+(fx0+fr10+3)*sr2+fr21; 如果r2的選擇順序在r1之前： =t+(fx0+1)*sr2+fr21+(fx0+fr20+3)*sr1+fr11; ,相減得：-=(fr10+2)*sr2-(fr20+2)*sr1; 如

31、果-0，我們應(yīng)該先選擇r1,否則先選擇r2。 問(wèn)題求解任意兩相鄰兒子間的順序可以確定下來(lái)，且與其它兒子無(wú)關(guān)?？蓪?duì)相鄰兒子調(diào)整順序，直到最優(yōu)，即排序，復(fù)雜度降為O(nklog2k) N個(gè)連通的小村編號(hào)從1到N，組成一顆樹(shù)。山賊總部設(shè)在編號(hào)為1的小村落中。其他的P個(gè)部門(mén)將在其它小村建立分部。分部還可以建在同一個(gè)小村落中。 每個(gè)分部到總部的路徑稱(chēng)為這個(gè)部門(mén)的管轄范圍，這P個(gè)分部的管轄范圍可能會(huì)重疊。在不同的村落建設(shè)不同的分部需要的花費(fèi)不同。每個(gè)部門(mén)可對(duì)他的管轄范圍內(nèi)的小村落收費(fèi)，但是不同的分部如果對(duì)同一小村落同時(shí)收費(fèi)時(shí)，可能會(huì)少收，但也可能多收。求：山賊集團(tuán)能夠獲得的最大的收益。1=N=100，1=

32、P=12，答案的絕對(duì)值不超過(guò)108。山賊集團(tuán)12543 樣例共建設(shè)兩個(gè)分部，兩個(gè)分部如果管理同一個(gè)節(jié)點(diǎn)，收益會(huì)增加10。每個(gè)節(jié)點(diǎn)的建設(shè)代價(jià)為節(jié)點(diǎn)旁邊的數(shù)。題意分析 最優(yōu)解顯然是在5號(hào)節(jié)點(diǎn)建設(shè)兩個(gè)分部，他們同時(shí)管理了1、2、5節(jié)點(diǎn)，修建花費(fèi)為4，因此總收益為26.3,32,23,32,23,2 定義fi,j為以i節(jié)點(diǎn)為根的子樹(shù)中，建立的分部情況為j的最大收益。fi,j =max(fi,j,fi,x+fk,j xor x-wI,x-wI,j xor x)+wi,j 用兒子刷新以后再用根去刷新一下，注意減掉修建的費(fèi)用。 x為j的子集，k為i的子節(jié)點(diǎn)，表示在以i為根的子樹(shù)中，以k為根的子樹(shù)的建立狀態(tài)為

33、j xor x，其余為x的最大收益。 wi,j為以i節(jié)點(diǎn)為根的子樹(shù)的管理狀態(tài)為j時(shí)的收益?？梢灶A(yù)處理出來(lái)。答案即為f(1,2p-1)。子集的枚舉技巧？(需預(yù)處理)for (int x=s;x;x=(x-1)&s) 問(wèn)題求解網(wǎng)絡(luò)收費(fèi)NOI2006 給了你一棵滿(mǎn)二叉樹(shù)（共2N個(gè)結(jié)點(diǎn)）,每個(gè)葉節(jié)點(diǎn)有一個(gè)類(lèi)型(A或B),任意兩個(gè)葉節(jié)點(diǎn)有一個(gè)流量Fij,他們的花費(fèi)就是k* Fij ,k為系數(shù)，由這兩個(gè)葉子結(jié)點(diǎn)的最近公共祖先P為根的子樹(shù)中所有葉節(jié)點(diǎn)中A類(lèi)型和B類(lèi)型的點(diǎn)的個(gè)數(shù)來(lái)確定?，F(xiàn)在你可以改變每個(gè)葉節(jié)點(diǎn)的類(lèi)型,需要花費(fèi)Ci ,任務(wù)是使所有花費(fèi)之和最小。數(shù)據(jù)規(guī)模和約定40%的數(shù)據(jù)中N4；80%的數(shù)

34、據(jù)中N7；100%的數(shù)據(jù)中N10,0Fij500,0Ci500 000i付費(fèi)付費(fèi)方式方式j(luò)付費(fèi)付費(fèi)方式方式nA和和nB關(guān)系關(guān)系系數(shù)系數(shù)K實(shí)際實(shí)際付費(fèi)付費(fèi)AAnA=nB0AB1BA1BB27 81 2 3 4 5 6PPABBBAAAA題意分析 我們用樹(shù)型動(dòng)規(guī)的一般方法來(lái)找問(wèn)題的解（先不考慮修改）比如要求P為根的樹(shù)的費(fèi)用，我們嘗試用子樹(shù)的費(fèi)用來(lái)計(jì)算P的費(fèi)用，我們發(fā)現(xiàn)P的費(fèi)用除了子樹(shù)的費(fèi)用之和外還要加上兩樹(shù)之間的結(jié)點(diǎn)產(chǎn)生的費(fèi)用。兩樹(shù)之間的費(fèi)用如何計(jì)算？問(wèn)題分析X7 81 2 3 4 5 6YQPABBBAAAA表格上給出的是點(diǎn)對(duì)之間的收費(fèi)系數(shù)，我們不能在子樹(shù)上考慮其它子樹(shù)的結(jié)點(diǎn)性質(zhì)。我們希望把系數(shù)

35、的計(jì)算定在本子樹(shù)的節(jié)點(diǎn)上。X7 81 2 3 4 5 6YQPABBBAAAA分析得，1號(hào)結(jié)點(diǎn)是否對(duì)3、4號(hào)結(jié)點(diǎn)產(chǎn)生收費(fèi)跟P這棵樹(shù)上A收費(fèi)結(jié)點(diǎn)和B收費(fèi)結(jié)點(diǎn)的個(gè)數(shù)有關(guān)。A個(gè)數(shù)少則A點(diǎn)收費(fèi)，B個(gè)數(shù)少于等于A(yíng)，則B點(diǎn)收費(fèi)1號(hào)結(jié)點(diǎn)是否對(duì)2號(hào)結(jié)點(diǎn)收費(fèi)取決于X這個(gè)樹(shù)的性質(zhì)（A多還是B多），是否對(duì)3、4收費(fèi)，取決于P這棵樹(shù)的性質(zhì)，同樣Q樹(shù)的性質(zhì)決定了是否對(duì)58收費(fèi)。問(wèn)題分析 每個(gè)結(jié)點(diǎn)怎么付費(fèi)，與它的所有祖先的性質(zhì)有關(guān)。把祖先的狀態(tài)定下來(lái)，則收費(fèi)就全部轉(zhuǎn)移到結(jié)點(diǎn)上，不再與外界有關(guān)。定義狀態(tài)fi,j,表示以i為根的樹(shù)，祖先狀態(tài)為j時(shí)應(yīng)付的費(fèi)用,可以換一種方法計(jì)算沒(méi)有修改的答案了。因每個(gè)節(jié)點(diǎn)可以修改，所以雖然祖先

36、定下來(lái)，但每個(gè)葉子節(jié)點(diǎn)的狀態(tài)變成兩個(gè)。每個(gè)節(jié)點(diǎn)還需要記葉子節(jié)點(diǎn)的狀態(tài)。狀態(tài)數(shù)太大！但不用記具體狀態(tài)，只需記兒子個(gè)數(shù)。定義狀態(tài)fi,j,k表示以i為根的樹(shù)，葉節(jié)點(diǎn)有j個(gè)A，祖先為k的最少付費(fèi)。轉(zhuǎn)移方程：fi,j,k = min(fson,j1,k1)，其中j1=j，k1為k加上節(jié)點(diǎn)i的狀態(tài)問(wèn)題求解 空間復(fù)雜度為O(2(n+1)*2(n+1)*2n)= O(2(3n+2)，超內(nèi)存，需要優(yōu)化。通過(guò)將樹(shù)分層發(fā)現(xiàn)從根每下一層，父節(jié)點(diǎn)多1個(gè)，但是兒子少2個(gè)，所以狀態(tài)雖然是3維,但j和k不能同時(shí)達(dá)到最大，可以直接動(dòng)態(tài)的將兒子狀態(tài)j與父親的的狀態(tài)k壓成一維。因?yàn)閮鹤幼疃?x個(gè)(x表示層數(shù))，狀態(tài)有2x+1個(gè)，

37、父親最多2(n-x)個(gè)，所以壓縮過(guò)后的狀態(tài)的最多就有O(2(n+1) )，總空間復(fù)雜度為O(2(2n+2)。 時(shí)間復(fù)雜度： 遍歷樹(shù)要O(2(n+1),枚舉兒子平均約為O(n)，枚舉k要O(2n),所以總時(shí)間復(fù)雜度是O(2n2(2n)。 問(wèn)題分析Ksenia and Combinatorics一棵有n個(gè)點(diǎn)的二叉樹(shù)，每一個(gè)點(diǎn)的編號(hào)為1n且各不相同，其中1號(hào)點(diǎn)為根節(jié)點(diǎn)詢(xún)問(wèn)存在多少種不同的樹(shù)，滿(mǎn)足樹(shù)的最大匹配邊數(shù)剛好為k最大匹配是指在樹(shù)上選擇盡量多的邊且滿(mǎn)足任意兩條邊不含有公共點(diǎn)答案對(duì)109 + 7取模1n,k50問(wèn)題分析 如何求解給定樹(shù)的最大匹配？ 如何不重不漏的計(jì)數(shù)？問(wèn)題求解 首先考慮如何求樹(shù)的最

38、大匹配 我們可以考慮動(dòng)態(tài)規(guī)劃方程fi0/1表示節(jié)點(diǎn)i是否被選時(shí)的最大匹配數(shù)。 轉(zhuǎn)移：fi0 = fu1fi1 = fu1 min( fu1 - fu0 )+1其中u為i的子節(jié)點(diǎn)問(wèn)題求解 令dpijk表示i個(gè)節(jié)點(diǎn)的有根樹(shù)，不選根節(jié)點(diǎn)的最大匹配數(shù)為j，選根節(jié)點(diǎn)的最大匹配數(shù)為k的樹(shù)的方案總數(shù)。 一棵樹(shù)選和不選根節(jié)點(diǎn)的最大配數(shù)最多相差1，那么重新定義狀態(tài)dpijadd，add=0/1,表示是否相多1。問(wèn)題求解 轉(zhuǎn)移： 枚舉左兒子的大小S及左兒子不選根節(jié)點(diǎn)的最大 匹配數(shù)ma, 令CC(i-S-1)*S*C(i-1,S);選和不選根節(jié)點(diǎn)的最大匹配數(shù)相差1：dpij1=(dpSma0*dpi-S-1j-ma

39、-11*CC+dpSma-11*dpi-S-1j-ma0*CC+dpSma0*dpi-S-1j-ma0*CC)選和不選根節(jié)點(diǎn)的最大匹配數(shù)相等：dpij0=dpSma-11*dpi-S-1j-ma-11*CC問(wèn)題求解每次轉(zhuǎn)移時(shí)枚舉左子樹(shù)的大小時(shí)保證左子樹(shù)大小右子樹(shù)大小，這樣保證不重復(fù)也不漏掉的統(tǒng)計(jì)答案了特殊的，當(dāng)左子樹(shù)等于右子樹(shù)時(shí)，除以2即可。邊界條件：Dp100=1；Dp101=0復(fù)雜度分析：Dp的狀態(tài)數(shù)為O(n k)轉(zhuǎn)移數(shù)為O(nk)所以復(fù)雜度為O(n2 k2)Three Trees 給你三棵樹(shù)，要求你在三棵樹(shù)中加入兩條邊，使之形成一棵新樹(shù)。我們定義樹(shù)的權(quán)值為樹(shù)中任意兩點(diǎn)之間的距離之和，詢(xún)問(wèn)

40、通過(guò)加邊最大能得到權(quán)值為多大的新樹(shù)。 三棵樹(shù)的初始大小分別為n1，n2，n3 注意加入兩條邊后必須構(gòu)成一棵新的樹(shù) 1 n1，n2，n3 105問(wèn)題分析 對(duì)于在三棵樹(shù)中加入兩條邊我們可以發(fā)現(xiàn)會(huì)存在三種情況。 設(shè)三棵樹(shù)從左到右依次為T(mén)1，T2， T3。 我們把三棵樹(shù)排為一排，考慮兩邊兩棵樹(shù)向中間的樹(shù)建邊，中間那棵樹(shù)可以是T1，T2或T3，所以一共有三種情況。 我們只用考慮在三種情況中取max即可，所以我們接下來(lái)只討論兩邊兩棵樹(shù)向中間那棵樹(shù)建邊的情況。 已知哪棵樹(shù)連了兩條邊，怎么求優(yōu)解？問(wèn)題求解 我們假設(shè)我們選擇了T1中一個(gè)點(diǎn)A，T2中兩個(gè)點(diǎn)B, C和T3中一個(gè)點(diǎn)D 此時(shí)我們連接A, B和C,D，我

41、們可以使用一個(gè)公式統(tǒng)計(jì)出答案。 設(shè)D1為T(mén)1中所有點(diǎn)到A的距離和，D2為T(mén)2中所有點(diǎn)到B的和，D3為T(mén)2中所有點(diǎn)到C的距離和，D4為T(mén)3中所有點(diǎn)到D的距離和，L為B到C的距離。Sum為三棵樹(shù)每棵樹(shù)內(nèi)部所有點(diǎn)的距離和。 那么，最終的答案為Ans = D4 (n1 + n2) + D1 (n2 + n3) + L n1 n3 + D2 n1 + D3 n3 + Sum問(wèn)題求解 根據(jù)Ans的公式，我們會(huì)發(fā)現(xiàn)只存在變量D1，D2，D3，D4和L而且D1和D4分別與其他變量獨(dú)立，即它們的取值不會(huì)影響到其他變量的取值。 所以我們可以貪心的使D1和D4盡量的大，這需要在T1和T3中DP出即可，這個(gè)問(wèn)題可以O(shè)

42、(n)的時(shí)間內(nèi)解決。 對(duì)于D2和D3兩者的取值共同影響著L，如果不能將對(duì)L的影響分開(kāi)統(tǒng)計(jì)，那么將會(huì)存在O(n2)的復(fù)雜度下界。 所以我們需要考慮如何分開(kāi)統(tǒng)計(jì)問(wèn)題求解123456789 對(duì)于任意兩個(gè)點(diǎn)B，C 我們發(fā)現(xiàn)B與C之間的距離可以拆成兩點(diǎn)到它們LCA的距離之和。 我們?cè)O(shè)B到LCA距離為l1 設(shè)C到LCA的距離為l2 則L = l1 + l2 B與C對(duì)答案的貢獻(xiàn)可以分開(kāi)計(jì)算：SumB = D2n1 + l1n1n3SumC = D3n3 + l2n1n3問(wèn)題求解 所以在中間那棵樹(shù)上，我們可以枚舉選擇的兩個(gè)點(diǎn)的LCA來(lái)計(jì)算答案。 對(duì)于樹(shù)上每一個(gè)節(jié)點(diǎn)我們記錄兩個(gè)信息maxB和maxC分別表示在以這個(gè)節(jié)點(diǎn)為根的子樹(shù)中能選擇到最大的SumB和SumC是多少。 對(duì)于每個(gè)枚舉的點(diǎn)t我們只用掃一遍它的所有子節(jié)點(diǎn)即可計(jì)算出t的maxB和maxC并同時(shí)求出以t為L(zhǎng)CA的B與C中SumB + SumC最大是多少。 這個(gè)步驟總共需要O(n)的時(shí)間問(wèn)題求解復(fù)雜度分析：因?yàn)樗胁襟E的復(fù)雜度都是O(n)的所以整個(gè)問(wèn)題能夠在O(n)的時(shí)間內(nèi)解決。參考代碼typedef long long lld;lld dfs(int x) visx = true; lld ret, v1, v2; PDx = (lld)n1 * totaldis