【正文】 度為O(1)，處理詢(xún)問(wèn)的復(fù)雜度為O(M2)，空間復(fù)雜度為O(M+N)。按照從大到小的順序之前先對(duì)其區(qū)間進(jìn)行統(tǒng)計(jì)，利用線段樹(shù)或樹(shù)狀數(shù)組?！緮?shù)據(jù)組織方案二】我們從特殊情況考慮：假設(shè)我們?cè)谙雀闅v序中，需要統(tǒng)計(jì)元素k，并且k所在區(qū)間里的元素都比它大。這樣，預(yù)處理可以用一個(gè)歸并排序，求得樹(shù)上所有區(qū)間的有序表。我們給出一個(gè)例子：同一棵子樹(shù)構(gòu)成一個(gè)連續(xù)的區(qū)間，這正方便了我們的統(tǒng)計(jì)。我們得到的啟示：憑第一感覺(jué)想出來(lái)的模型不一定是最好的，對(duì)于一個(gè)題目，我們充分挖掘其數(shù)據(jù)關(guān)系并加以利用，合理地組織數(shù)據(jù)并且嘗試用已有的知識(shí)來(lái)解決，推陳出新，才能不斷地進(jìn)步。并且，這個(gè)算法模型對(duì)于以前有很多類(lèi)似的樹(shù)形動(dòng)態(tài)規(guī)劃題目都適用，這是我們?cè)诜治霰绢}的過(guò)程中的意外收獲。思考并總結(jié)上面的結(jié)論：對(duì)于一個(gè)主件，我們?nèi)绻毁?gòu)買(mǎi)的話，那么其附件我們都不用考慮，而直接“跳”到下一個(gè)主件。而利用了題目特殊條件的算法2和算法3，直接套用算法肯定是行不通的。原本樹(shù)上的問(wèn)題經(jīng)過(guò)我們“合理地組織數(shù)據(jù)以后”，成功地轉(zhuǎn)化成了一個(gè)序列上的問(wèn)題。任務(wù)　購(gòu)買(mǎi)一些物品，總價(jià)格不超過(guò)M，使得被購(gòu)買(mǎi)的物品的權(quán)值之和最大。對(duì)于每一組，可能的購(gòu)買(mǎi)方案最多只有：這樣，我們可以借鑒經(jīng)典的01背包動(dòng)態(tài)規(guī)劃，把每一組看作一個(gè)對(duì)象，取值和花費(fèi)對(duì)應(yīng)最多五種。這樣枚舉的效率顯然不高！我們可以用左兒子右兄弟表示法來(lái)表示這一棵樹(shù)，將原樹(shù)轉(zhuǎn)化成二叉樹(shù)，則我們?cè)谶M(jìn)行狀態(tài)轉(zhuǎn)移的時(shí)候只用考慮給左兒子分配多少錢(qián)。任務(wù)　購(gòu)買(mǎi)一些物品，總價(jià)格不超過(guò)M，使得被購(gòu)買(mǎi)的物品的權(quán)值之和最大。不同的是HASH表和TRIE是利用數(shù)據(jù)形式的重新組織，而預(yù)排序＋二分查找是通過(guò)對(duì)數(shù)據(jù)順序的重新組織來(lái)達(dá)到優(yōu)化算法的目的的。淺談數(shù)據(jù)的合理組織 【摘要】信息學(xué)是一門(mén)高深的學(xué)科，它正在高速的發(fā)展。當(dāng)然我們有很多已知的辦法：HASH表、TRIE、預(yù)排序+二分查找……這些算法都是通過(guò)對(duì)數(shù)據(jù)進(jìn)行合理的組織而起到了減少工作量的作用。我們稱(chēng)可以直接被購(gòu)買(mǎi)的物品為主件，稱(chēng)不能被直接購(gòu)買(mǎi)的物品為附件，附件只有當(dāng)其主件被購(gòu)買(mǎi)了才能被購(gòu)買(mǎi)，一個(gè)主件最多有兩個(gè)附件，附件沒(méi)有下一級(jí)附件。其中ci為a的子節(jié)點(diǎn)；∑bi=bcost[a]。這樣，顯然對(duì)于（圖一）中每一組（主件＋附件），可以作為整體考慮。每個(gè)物品都有一個(gè)權(quán)值(50000)?？此坪驮瓉?lái)的條件沒(méi)有什么變化，但是實(shí)際上我們給節(jié)點(diǎn)的位置已經(jīng)加上了一個(gè)限制。我們依然試著從前面的題目中尋找算法：我們可以直接套用算法1，因?yàn)樵撍惴ㄕ脤?shù)據(jù)作為樹(shù)結(jié)構(gòu)來(lái)進(jìn)行處理。上圖中，對(duì)于附件a，實(shí)際上一個(gè)k=0的狀態(tài)傳遞下去是沒(méi)有意義的，因?yàn)楦郊和附件c也必然不能被購(gòu)買(mǎi)。狀態(tài)轉(zhuǎn)移：對(duì)于一個(gè)節(jié)點(diǎn)，我們考慮是否購(gòu)買(mǎi)它：購(gòu)買(mǎi)：那么我們繼續(xù)考慮它后面的節(jié)點(diǎn)不購(gòu)買(mǎi)：那么我們跳過(guò)它的子孫節(jié)點(diǎn)方程如下：F[i][j]=Max{F[i+1][jcost[list[i]]]+weight[list[i]],F[i+count[list[i]]][j]}這個(gè)算法依然是O(NM)的，很完美地解決了本題。這正是樹(shù)形動(dòng)態(tài)規(guī)劃算法的瓶頸所在！而我們利用樹(shù)的先根遍歷序?qū)⑥D(zhuǎn)樹(shù)形轉(zhuǎn)化為線形序列，成功地避免了樹(shù)形形態(tài)的限制，正是合理地組織數(shù)據(jù)。既然沒(méi)有辦法改造數(shù)據(jù)結(jié)構(gòu)，那么我們轉(zhuǎn)換數(shù)據(jù)形態(tài)——把樹(shù)轉(zhuǎn)化為序列再進(jìn)行統(tǒng)計(jì)，先根遍歷序即是我們轉(zhuǎn)換后的理想形態(tài)。當(dāng)然我們可以構(gòu)造出一種比較有效的嵌套數(shù)據(jù)結(jié)構(gòu)——以有序表為元素的線段樹(shù)，如圖： 其中，線段樹(shù)的每一個(gè)節(jié)點(diǎn)是對(duì)應(yīng)區(qū)間的元素以權(quán)值為關(guān)鍵字的有序表?？倳r(shí)間復(fù)雜度為O(Nlog22(N))，空間復(fù)雜度為O(Nlog2(N))。所以區(qū)間中的元素個(gè)數(shù)即為比待插入元素大的元素個(gè)數(shù)。1 ≤ N ≤ 3 * 1041 ≤ M ≤ 1051 ≤ Q ≤ 105【問(wèn)題分析】顯然，我們可以輕松地設(shè)計(jì)出一個(gè)樸素的算法：用隊(duì)列保存所有邊，當(dāng)遇到刪邊操作時(shí)加上刪除標(biāo)記（利用HASH我們可以做到O(1))，遇到詢(xún)問(wèn)操作時(shí)則枚舉刪邊然后用并查集判斷AB是否連通。這跟我們的題目有什么關(guān)系呢？顯然，同一個(gè)重連通分量(塊)中的任意兩點(diǎn)之間都沒(méi)有關(guān)鍵邊。那么AB間的距離Dis(A,B)=Depth[A]+Depth[B]2*Depth[LCA(A,B)]注意一個(gè)細(xì)節(jié)，即我們把一個(gè)重連通分量“縮”成一個(gè)節(jié)點(diǎn)時(shí)，事實(shí)上是把分量里面的所有點(diǎn)的深度都設(shè)為它們中最小的那個(gè)深度，即往上提升(在同一個(gè)重連通分量中以深度最小的點(diǎn)作其它點(diǎn)的代表)?！具M(jìn)一步組織數(shù)據(jù)】現(xiàn)在的問(wèn)題是我們需要快速地將一個(gè)塊進(jìn)行重新求塊，似乎是沒(méi)有現(xiàn)成的辦法?，F(xiàn)在我們來(lái)考慮細(xì)節(jié)實(shí)現(xiàn)：我們需要用到LCA，當(dāng)然可以用中序遍歷+RMQ實(shí)現(xiàn)。我們最初利用“收縮”的思想，把圖整理成為一棵樹(shù)，然后又巧妙地將數(shù)據(jù)從后往前處理，把原題中的“刪邊操作”操作變成了“加邊操作”。這正是我們前進(jìn)的動(dòng)力，思想的源泉。附件無(wú)如果要買(mǎi)歸類(lèi)為附件的物品，必須先買(mǎi)該附件所屬的主件。（其中*為乘號(hào)）　　請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿(mǎn)足要求的購(gòu)物單。這天，兩只小蟲(chóng)Nileh和Nixed決定一起分享一棵果樹(shù)。(１號(hào)分叉即樹(shù)根，它沒(méi)有上級(jí)分叉點(diǎn)）輸入文件的第n+i(1=i=n)行一個(gè)正數(shù)ai,表示生長(zhǎng)在i號(hào)分叉上的果實(shí)的美味值。顯然上圖中，1號(hào)與5號(hào)星球之間的關(guān)鍵航線有1條：即為45航線。隨后有M行，每行有兩個(gè)不相同的整數(shù)A、B表示在星球A與B之間存在一條