【正文】 隨后有M行，每行有兩個不相同的整數(shù)A、B表示在星球A與B之間存在一條航線。(１號分叉即樹根，它沒有上級分叉點(diǎn)）輸入文件的第n+i(1=i=n)行一個正數(shù)ai,表示生長在i號分叉上的果實(shí)的美味值。（其中*為乘號）　　請你幫助金明設(shè)計(jì)一個滿足要求的購物單。附件我們最初利用“收縮”的思想，把圖整理成為一棵樹，然后又巧妙地將數(shù)據(jù)從后往前處理，把原題中的“刪邊操作”操作變成了“加邊操作”?！具M(jìn)一步組織數(shù)據(jù)】現(xiàn)在的問題是我們需要快速地將一個塊進(jìn)行重新求塊，似乎是沒有現(xiàn)成的辦法。這跟我們的題目有什么關(guān)系呢？顯然，同一個重連通分量(塊)中的任意兩點(diǎn)之間都沒有關(guān)鍵邊。所以區(qū)間中的元素個數(shù)即為比待插入元素大的元素個數(shù)。當(dāng)然我們可以構(gòu)造出一種比較有效的嵌套數(shù)據(jù)結(jié)構(gòu)——以有序表為元素的線段樹，如圖： 其中，線段樹的每一個節(jié)點(diǎn)是對應(yīng)區(qū)間的元素以權(quán)值為關(guān)鍵字的有序表。這正是樹形動態(tài)規(guī)劃算法的瓶頸所在！而我們利用樹的先根遍歷序?qū)⑥D(zhuǎn)樹形轉(zhuǎn)化為線形序列，成功地避免了樹形形態(tài)的限制，正是合理地組織數(shù)據(jù)。上圖中，對于附件a，實(shí)際上一個k=0的狀態(tài)傳遞下去是沒有意義的，因?yàn)楦郊和附件c也必然不能被購買?？此坪驮瓉淼臈l件沒有什么變化，但是實(shí)際上我們給節(jié)點(diǎn)的位置已經(jīng)加上了一個限制。這樣，顯然對于（圖一）中每一組（主件＋附件），可以作為整體考慮。我們稱可以直接被購買的物品為主件，稱不能被直接購買的物品為附件，附件只有當(dāng)其主件被購買了才能被購買，一個主件最多有兩個附件，附件沒有下一級附件。淺談數(shù)據(jù)的合理組織 【摘要】信息學(xué)是一門高深的學(xué)科，它正在高速的發(fā)展。任務(wù)　購買一些物品，總價(jià)格不超過M，使得被購買的物品的權(quán)值之和最大。對于每一組，可能的購買方案最多只有：這樣，我們可以借鑒經(jīng)典的01背包動態(tài)規(guī)劃，把每一組看作一個對象，取值和花費(fèi)對應(yīng)最多五種。原本樹上的問題經(jīng)過我們“合理地組織數(shù)據(jù)以后”，成功地轉(zhuǎn)化成了一個序列上的問題。思考并總結(jié)上面的結(jié)論：對于一個主件，我們?nèi)绻毁徺I的話，那么其附件我們都不用考慮，而直接“跳”到下一個主件。我們得到的啟示：憑第一感覺想出來的模型不一定是最好的，對于一個題目，我們充分挖掘其數(shù)據(jù)關(guān)系并加以利用，合理地組織數(shù)據(jù)并且嘗試用已有的知識來解決，推陳出新，才能不斷地進(jìn)步。這樣，預(yù)處理可以用一個歸并排序，求得樹上所有區(qū)間的有序表。按照從大到小的順序之前先對其區(qū)間進(jìn)行統(tǒng)計(jì)，利用線段樹或樹狀數(shù)組。并且，對于兩個不同的重連通分量M1,M2：在進(jìn)行刪邊操作以前，詢問任意分屬這兩個分量的兩點(diǎn)A∈M1,B∈M2，詢問的結(jié)果都是一樣的，即結(jié)果只跟分量間的邊有關(guān)系。但是如果操作不是刪邊，而是加邊呢？顯然，在一棵樹上加上一條邊，必然產(chǎn)生環(huán)，伴隨著的就是新的重連通分量產(chǎn)生。既有“形態(tài)”，又有“順序”上的考慮。電腦【輸入文件】　　 的第1行，為兩個正整數(shù)，用一個空格隔開：　　N（每個果子的美味值不相等）【輸出格式】輸出共n行，每行三個數(shù)，分別表示咬掉第i個果實(shí)后上面部分、下面部分、從樹根到這個分叉點(diǎn)的路徑中比它美味的果實(shí)數(shù)。接下來每行有三個整數(shù)C、A、B。表示有N個星球（1 N 30000），初始時已經(jīng)有M條航線（1 M 100000）?！据斎敫袷健枯斎胛募谝恍惺且粋€整數(shù)n(n=105)表示樹的分叉數(shù)（包括樹根）輸入文件的第i行一個數(shù)pi，表示分叉i的上一級分叉的編號(pii)?！　≡O(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：　　v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]?！拘〗Y(jié)】這是一道很經(jīng)典的題目。我們當(dāng)然可以只對被刪邊所在的塊進(jìn)行處理，但是最壞情況下還是和每次求一次塊是一樣的。也就是說樹上的任意一條邊都是關(guān)鍵邊。從大到小保證了現(xiàn)有的所有元素都比待插入的元素大。下面我們研究轉(zhuǎn)化后的問題：【數(shù)據(jù)組織方案一】我們不對數(shù)據(jù)進(jìn)行更深入的組織，直接利用先根遍歷序，強(qiáng)制用數(shù)據(jù)結(jié)構(gòu)來進(jìn)行統(tǒng)計(jì)。也就是說：樹的形態(tài)決定了在狀態(tài)轉(zhuǎn)移的時候要進(jìn)行額外的枚舉。如果i是附件，那么實(shí)際上在到達(dá)下一個主件以前，i后面的附件是都不會被購買的。如下圖：這樣做的好處是：一個附件能被購買的必要條件就是在其前面的最近的主件被購買了。［例一］金明的預(yù)算方案及其加強(qiáng)版金明的預(yù)算方案【題意描述】給出N個物品，每個物品都有一個權(quán)值(50000)和一個價(jià)格(10000)。隨著信息學(xué)的發(fā)展，其題目中的關(guān)系也變得越來越錯宗復(fù)雜，給我們解題帶來困難。N3200 M60【簡要分析】我們很容易聯(lián)想到經(jīng)典的動態(tài)規(guī)劃之01背包問題?！舅惴ǘ縞ost[i][k]表示分組后第i個對象的第k種購買方案的花費(fèi)?！舅惴?】這樣組織數(shù)據(jù)以后，我們利用前面提到的條件“一個附件能被購買的必要條件是其前面的最近的主件被購買了”，可以輕松地設(shè)計(jì)動態(tài)規(guī)劃算法：定義：cost[i]表示第i個物品的價(jià)格weight[i]表示第i個物品的權(quán)值F[i][j][k]表示從第i個物品到第n個物品，最多花費(fèi)j元，第i個物品前的主件有(k=1)沒有(k=0)被購買。我們把它應(yīng)用到本題中來：重要結(jié)論　我們考慮一棵子樹的時候，如果我們不購買其根節(jié)點(diǎn)，那么其子樹中所有節(jié)點(diǎn)我們都不必討論了。前面我們在樹據(jù)的組織結(jié)構(gòu)上進(jìn)行了合理地