樹上差分在競賽中的應(yīng)用NOIPCSP-SACM-ICPC

樹上差分/NOIP/CSP_S/ACM-ICPC樹上差分樹上差分的基本操作就是對樹上的一段路徑或鏈進(jìn)行區(qū)間查詢。如果是針對點(diǎn)權(quán)的查詢，被稱為點(diǎn)差分；如果是對邊權(quán)的查詢，被稱為邊差分。樹上差分就是利用差分的性質(zhì)，對路徑上的重要節(jié)點(diǎn)進(jìn)行修改，而不是暴力全改。通過深度優(yōu)先搜索遍歷求出差分?jǐn)?shù)組的前綴和，可以達(dá)到降低復(fù)雜度的目的。樹上差分可以多次對樹的一個路徑進(jìn)行修改，并在最后詢問某一節(jié)點(diǎn)或區(qū)間的結(jié)果。修改的時間復(fù)雜度是O(1),查詢的時間復(fù)雜度為O(N)。點(diǎn)差分若將樹上兩點(diǎn)u,v之間路徑上的所有點(diǎn)的點(diǎn)權(quán)增加x。令o是點(diǎn)u,v的最近公共祖先，即o=LCA(u,v)。o的父親節(jié)點(diǎn)為p。則差分操作如下：在節(jié)點(diǎn)u和節(jié)點(diǎn)v的位置增加點(diǎn)權(quán)x，即d[u]+=x,d[v]+=x；在節(jié)點(diǎn)u和節(jié)點(diǎn)v的最近公共祖先o的位置，以及o的父親節(jié)點(diǎn)p，調(diào)減點(diǎn)權(quán)x，即d[o]-=x,d[p]-=x。這樣dfs遍歷統(tǒng)計以每個節(jié)點(diǎn)為根的子樹的子節(jié)點(diǎn)權(quán)值和，即當(dāng)前節(jié)點(diǎn)的最終權(quán)值。這個考慮思路類似于對于一個數(shù)列的差分/前綴和的關(guān)系。邊差分對路徑上的邊權(quán)進(jìn)行差分的過程叫做樹的邊差分。由于差分操作只能將權(quán)值放在點(diǎn)上，所以習(xí)慣上將邊的權(quán)值存在深度更深（靠下）的節(jié)點(diǎn)上。邊差分存在子節(jié)點(diǎn)中的原因是，因?yàn)樽庸?jié)點(diǎn)具有唯一性。 若將樹上兩點(diǎn)u,v之間路徑上的所有邊權(quán)增加x。如上，令o=LCA(u,v)，以每條邊兩端深度較大的節(jié)點(diǎn)存儲該邊的差分?jǐn)?shù)組。則操作如下：d[u]+=x,d[v]+=x,d[o]-=2*x。此處和點(diǎn)差分不同。可以理解為d[o]存儲的是邊(o,p)的權(quán)值，其中p為o的父親節(jié)點(diǎn)，這個權(quán)值不在點(diǎn)u,v之間的路徑上，所以可以一次性調(diào)減完成。同樣dfs遍歷統(tǒng)計以每個節(jié)點(diǎn)為根的樹的節(jié)點(diǎn)的權(quán)值和，就是當(dāng)前節(jié)點(diǎn)到父親節(jié)點(diǎn)的邊的最終權(quán)值。例題：最大流農(nóng)夫約翰給他的牛棚的N個隔間之間安裝了N?1根管道，隔間編號從1到N。所有隔間都被管道連通了。農(nóng)夫約翰有K條運(yùn)輸牛奶的路線，第i條路線從隔間si運(yùn)輸?shù)礁糸gti。一條運(yùn)輸路線會給它的兩個端點(diǎn)處的隔間以及中間途徑的所有隔間帶來一個單位的運(yùn)輸壓力。你需要計算壓力最大的隔間的壓力是多少。第一行輸入兩個整數(shù)N和K。接下來N?1行每行輸入兩個整數(shù)x和y，其中x!=y。表示一根在牛棚x和y之間的管道。接下來K行每行兩個整數(shù)s和t，描述一條從s到t的運(yùn)輸牛奶的路線。輸出一個整數(shù)，表示壓力最大的隔間的壓力是多少。此題可以將n個隔間看作n個節(jié)點(diǎn)，節(jié)點(diǎn)之間n-1條管道可以理解為n條邊。那么顯然這是一顆樹。為什么是樹，請大家翻閱作者其他文章。題意很明顯是多次修改(k次)路徑si,ti之間的點(diǎn)權(quán)，最后查詢最大點(diǎn)權(quán)的點(diǎn)。這明顯是一個樹上點(diǎn)差分的板子題。篇幅所限，樣例、代碼請到作者主頁留言討論。謝謝。例題：松鼠的新家松鼠的新家是一棵樹，前幾天剛剛裝修了新家，新家有n個房間，并且有n?1根樹枝連接，每個房間都可以相互到達(dá)，且倆個房間之間的路線都是唯一的。天哪，他居然真的住在“樹”上。松鼠想邀請小熊維尼前來參觀，并且還指定一份參觀指南，他希望維尼能夠按照他的指南順序，先去a1，再去a2，……，最后到an，去參觀新家。 可是這樣會導(dǎo)致重復(fù)走很多房間，懶惰的維尼不停地推辭?？墒撬墒蟾嬖V他，每走到一個房間，他就可以從房間拿一塊糖果吃。維尼是個饞家伙，立馬就答應(yīng)了?，F(xiàn)在松鼠希望知道為了保證維尼有糖果吃，他需要在每一個房間各放至少多少個糖果。松鼠參觀指南上的最后一個房間an是餐廳，餐廳里他準(zhǔn)備了豐盛的大餐，所以當(dāng)維尼在參觀的最后到達(dá)餐廳時就不需要再拿糖果吃了。輸入第一行一個正整數(shù)n，表示房間個數(shù)第二行n個正整數(shù)，依次描述a1,a2,?,an。n?1行，每行兩個正整數(shù)x,y，表示標(biāo)號x和y的兩個房間之間有樹枝相連。輸出一共n行，第i行輸出標(biāo)號為i的房間至少需要放多少個糖果，才能讓維尼有糖果吃。如上題，這是一道標(biāo)準(zhǔn)的樹上點(diǎn)差分模板題目。依舊是區(qū)間修改，區(qū)間查詢的老套路。區(qū)別是松鼠的參觀指南就是它修改的路徑。即隨著參觀路徑，進(jìn)行區(qū)間修改，最后對樹上的所有點(diǎn)進(jìn)行統(tǒng)計，即答案。篇幅所限，樣例、代碼請到作者主頁留言討論。謝謝。例題：運(yùn)輸計劃公元2044年，人類進(jìn)入了宇宙紀(jì)元。L國有n個星球，還有n?1條雙向航道，每條航道建立在兩個星球之間。這n?1條航道連通了L國的所有星球。小P掌管一家物流公司，該公司有很多個運(yùn)輸計劃，每個運(yùn)輸計劃形如：有一艘物流飛船需要從ui號星球沿最快的宇航路徑飛行到vi號星球去。顯然，飛船駛過一條航道是需要時間的，對于航道j，任意飛船駛過它所花費(fèi)的時間為tj，并且任意兩艘飛船之間不會產(chǎn)生任何干擾。為了鼓勵科技創(chuàng)新，L國國王同意小P的物流公司參與L國的航道建設(shè)，即允許小P把某一條航道改造成蟲洞，飛船駛過蟲洞不消耗時間。在蟲洞的建設(shè)完成前小P的物流公司就預(yù)接了m個運(yùn)輸計劃。在蟲洞建設(shè)完成后，這m個運(yùn)輸計劃會同時開始，所有飛船一起出發(fā)。當(dāng)這m個運(yùn)輸計劃都完成時，小P的物流公司的階段性工作就完成了。如果小P可以自由選擇將哪一條航道改造成蟲洞，試求出小P的物流公司完成階段性工作所需要的最短時間是多少？輸入第一行包括兩個正整數(shù)n,m（n,m<=2*10^5），表示L國中星球的數(shù)量及小P公司預(yù)接的運(yùn)輸計劃的數(shù)量，星球從1到n編號。接下來n?1行描述航道的建設(shè)情況，其中第i行包含三個整數(shù)ai,bi和ti，表示第i條雙向航道修建在ai與bi兩個星球之間，任意飛船駛過它所花費(fèi)的時間為ti。接下來m行描述運(yùn)輸計劃的情況，其中第j行包含兩個正整數(shù)uj和vj，表示第j個運(yùn)輸計劃是從uj號星球飛往vj號星球。輸出一個整數(shù)，表示小P的物流公司完成階段性工作所需要的最短時間。題目大意與上兩題類似，有許多條運(yùn)輸路徑，可以被看作一棵樹。然后給出一些點(diǎn)對?？紤]將某一條邊的權(quán)值變?yōu)?后，求點(diǎn)對間的最大距離最小，并給出最小值。題意中的完成工作，即所有工作的最長時間，即點(diǎn)對間的最大距離或權(quán)值。要求完整工作最短時間，即這個值最小。先不考慮樹上差分，一般最...最...的求值模型會考慮使用二分答案，特別是在上題的數(shù)據(jù)量前提下。具體可參見拙著《復(fù)雜二分在競賽中的應(yīng)用》。此處不贅述。求點(diǎn)對間的距離或權(quán)值，一般有三種方法：倍增、樹鏈剖分和Tarjan算法。內(nèi)容過于復(fù)雜，這里不做介紹。二分check()函數(shù)中會用到樹上差分。設(shè)當(dāng)前二分出來答案為x。以x值為基點(diǎn)觀察點(diǎn)對：對于dis[i]<=x的點(diǎn)對可以忽略。對于dis[i]>x的點(diǎn)對，需要統(tǒng)計（設(shè)計入變量num）并且刪掉路徑i上的一條邊。接下來考慮刪除最長距離路徑中的哪條邊。顯然，如果刪掉某條邊能使所有點(diǎn)對距離都小于等于x，那么這條邊的權(quán)值w[i]必然滿足大于等于max(dis[i])-x。需要統(tǒng)計滿足上條件的邊在dis[i]>x的點(diǎn)對路徑上的出現(xiàn)次數(shù)。這個環(huán)節(jié)就需要使用樹上差分了。對于點(diǎn)對(xi,yi)，設(shè)數(shù)組p[]記錄兩點(diǎn)間邊出現(xiàn)得次數(shù)。如果dis[i]>x，即第i條路徑滿足條件，則p[xi]++,p[yi]++,p[lca(xi,yi)]–=2。完成第i條路徑得區(qū)間修改。進(jìn)一步需要統(tǒng)計第i條路徑上點(diǎn)t的數(shù)組p[]的前綴和qz[t]。qz[t]就是結(jié)點(diǎn)t和其父親節(jié)點(diǎn)所連邊出現(xiàn)的次數(shù)。如果存在qz[t]>=num，說明找到了要去掉的邊。二分check返回真。x值再往大調(diào)整。否則說明沒有找到，則x往小調(diào)整。篇幅所限，樣例、代碼請到作者主頁留言討論。謝謝。例題：最小割一個具有n個節(jié)點(diǎn)和m條邊的簡單未加權(quán)圖G。圖G是一個既不包含環(huán)也不包含重邊的無向圖。設(shè)T是G的生成樹。如果G中的一個割只割T的一條邊，則說這個割是關(guān)于T的。題目要求找到圖G關(guān)于給定生成樹T的最小割。輸入包含幾個測試用例。第一行是單個整數(shù)t（1≤t≤5），即測試用例的數(shù)量。接下來是t個測試用例。每個測試用例包含幾行。第一行包含兩個整數(shù)n（2≤n≤20000）和m（n?1≤m≤200000）。下面的n?1行描述了生成樹T，每一行都包含對應(yīng)于一條邊的兩個整數(shù)u和v。接下來的m?n+1行描述無向圖G，并且它們中的每一行都包含兩個整數(shù)u和v，這兩個整數(shù)對應(yīng)于不在生成樹T中的邊。對于每個測試用例，您應(yīng)該輸出關(guān)于給定生成樹T的圖G的最小割。題意求圖G的最小割，但是這個割有且僅有生成樹T的一條邊。對于一棵樹，加上一條邊，會形成對應(yīng)的環(huán)。如果刪掉這個環(huán)上的邊，那么剛加上的那條邊也要刪掉。即如果刪掉這條樹邊，所對應(yīng)的最小邊集的數(shù)量要加1。那么把n-1條邊分配給點(diǎn)的思路就是樹剖，但是超時。換一種方法考慮。因?yàn)樯蓸銽中只有一條邊屬于割。那么割對生成樹T來說只是分成了兩個子樹。本題只需要