算法合集之《分治算法在樹的路徑問題中的應(yīng)用》

1、算法合集之分治算法在樹的路徑問題中的應(yīng)用算法合集之分治算法在樹的路徑問題中的應(yīng)用樹的路徑問題以路徑為詢問對象的題目 POJ1741,樹中點對統(tǒng)計SPOJ QTREE,FTOUR2,QTREE4Astar2008復(fù)賽 黑白樹算法合集之分治算法在樹的路徑問題中的應(yīng)用論文內(nèi)容論文內(nèi)容一、樹的分治算法樹的分治的兩種常見形式：基于點的分治 基于邊的分治二、樹的路徑剖分算法三、樹的分治算法的進(jìn)一步探討 如何改進(jìn)基于邊的分治的時間復(fù)雜度歸納為基于鏈的分治算法合集之分治算法在樹的路徑問題中的應(yīng)用一、樹的分治算法一、樹的分治算法 樹的分治算法是分治思想在樹型結(jié)構(gòu)上的體現(xiàn)。 ：除去樹中的某些對象，使原樹被分解成若

2、干互不相交的部分。算法合集之分治算法在樹的路徑問題中的應(yīng)用兩種常見的形式兩種常見的形式基于點的分治算法合集之分治算法在樹的路徑問題中的應(yīng)用兩種常見的形式兩種常見的形式基于點的分治1.選取一個點將無根樹轉(zhuǎn)為有根樹2.遞歸處理每一顆以根結(jié)點的兒子為根的子樹算法合集之分治算法在樹的路徑問題中的應(yīng)用兩種常見的形式兩種常見的形式基于邊的分治算法合集之分治算法在樹的路徑問題中的應(yīng)用兩種常見的形式兩種常見的形式基于邊的分治1.在樹中選取一條邊2. 將原有的樹分成兩棵不相交的樹，遞歸處理。 算法合集之分治算法在樹的路徑問題中的應(yīng)用效率分析效率分析 可以證明在基于點的分治中，如果每次都選取樹的重心，那么至多遞歸

3、 O(LogN)次。 基于邊的分治最壞情況下遞歸次數(shù)為O(N)。算法合集之分治算法在樹的路徑問題中的應(yīng)用【例一】樹中點對統(tǒng)計【例一】樹中點對統(tǒng)計 給定一棵N個結(jié)點的帶權(quán)樹。 定義dist(u，v)=u，v兩點間的路徑長度，路徑的長度定義為路徑上所有邊的權(quán)和。 給定一個K，如果對于不同的兩個結(jié)點a，b，如果滿足dist(a，b)K，則稱(a，b)為合法點對。 求合法點對個數(shù)。 N10000,K109算法合集之分治算法在樹的路徑問題中的應(yīng)用一條路徑：1.過根節(jié)點2.在一顆子樹內(nèi)遞歸處理樹中點對統(tǒng)計樹中點對統(tǒng)計算法合集之分治算法在樹的路徑問題中的應(yīng)用記D(i) 表示節(jié)點i到根節(jié)點路徑的長度Answe

4、r = 滿足 D(i)+D(j)K 的(i,j)個數(shù) i,j屬于不同的子樹O(NlogN)樹中點對統(tǒng)計樹中點對統(tǒng)計算法合集之分治算法在樹的路徑問題中的應(yīng)用時間復(fù)雜度分析時間復(fù)雜度分析每層的時間復(fù)雜度不超過O(NlogN)最多遞歸O(logN)次O(Nlog2N)算法合集之分治算法在樹的路徑問題中的應(yīng)用二、路徑剖分算法二、路徑剖分算法輕重邊路徑剖分 將樹中的邊分為兩類：輕邊和重邊。 記Size(U)表示以U為根的子樹的結(jié)點個數(shù)。 令V為U的兒子中Size(V)最大的一個，那么我們稱邊(U，V)為重邊，其余邊為輕邊。 算法合集之分治算法在樹的路徑問題中的應(yīng)用輕重邊路徑剖分輕重邊路徑剖分 我們稱某條

5、路徑為重路徑，當(dāng)且僅當(dāng)它全部由重邊組成。那么對于每個點到根的路徑上都不超過O(logN)條輕邊和O(logN)條重路徑。 我們稱某條路徑為重路徑，當(dāng)且僅當(dāng)它全部由重邊組成。那么對于每個點到根的路徑上都不超過O(logN)條輕邊和條輕邊和O(logN)條重路徑條重路徑。路徑剖分算法常用來高效的維護(hù)點到根的路徑 Spoj的Qtree,Astar2008的黑白樹算法合集之分治算法在樹的路徑問題中的應(yīng)用【例二】【例二】 Query On a Tree 給定一棵包含N個結(jié)點的樹，每個節(jié)點要么是黑色，要么是白色。要求模擬兩種操作： 1)改變某個結(jié)點的顏色。 2)詢問最遠(yuǎn)的兩個黑色結(jié)點之間的距離。數(shù)據(jù)范圍：

6、 N100000,邊權(quán)絕對值不超過1000 此題出自2007年浙江省選,但此題中樹的邊權(quán)可能為負(fù)，無法使用括號序列。另尋他法另尋他法算法合集之分治算法在樹的路徑問題中的應(yīng)用路徑剖分算法路徑剖分算法 這道題的算法似乎與路徑剖分毫無關(guān)系，那么我們是否能用路徑剖分算法解決此題呢？算法合集之分治算法在樹的路徑問題中的應(yīng)用路徑剖分與樹的分治的聯(lián)系路徑剖分與樹的分治的聯(lián)系一棵樹及其剖分算法合集之分治算法在樹的路徑問題中的應(yīng)用路徑剖分與樹的分治的聯(lián)系路徑剖分與樹的分治的聯(lián)系 路徑剖分每次刪除了一條鏈，所以路徑剖分算法可以看做是基于鏈的分治基于鏈的分治 按照點到根結(jié)點路徑上的輕邊個數(shù)分層擺放。遞歸樹！算法合集

7、之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree 將路徑剖分理解成基于鏈的分治后，我們可以用類似基于點的分治的方法將路徑分類。1.與鏈有重合部分2.與鏈沒有重合部分遞歸處理算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree 12N 我們的目標(biāo)就是要求出滿足與此鏈的重合部分在1,N的路徑的最大長度。 我們可以用線段樹解決這個問題。算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree 記D(i)表示第i個結(jié)點至子樹內(nèi)某個黑色結(jié)點的路徑中長度的最大值。Dist(i,j)表示鏈上的第i個點到第j個點的距離。算法合集之分治算法在樹的路徑問題中的應(yīng)用Qu

8、ery On a Tree 對于線段樹中的一個區(qū)間L,R,我們需要記錄下面三個量：)(),(iDiLDistMaxMaxL),()(RiDistiDMaxMaxR= 與此鏈的重合部分在L,R的路徑的最大長度OptLRLR算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree )() 1,(),()(RcMaxLMidLDistLcMaxLMaxPMaxLLRLRLR 設(shè)區(qū)間L,R的結(jié)點編號為P，Lc,Rc分別表示P的左右兩個兒子，區(qū)間L,Mid和Mid+1,R。我們可以得到如下轉(zhuǎn)移：算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree LRLRLR),()()

9、,()(RMidDistLcMaxRRcMaxRMaxPMaxR 設(shè)區(qū)間L,R的結(jié)點編號為P，Lc,Rc分別表示P的左右兩個兒子，區(qū)間L,Mid和Mid+1,R。我們可以得到如下轉(zhuǎn)移：算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree ) 1,()()(),(),()(MidMidDistRcMaxLLcMaxRRcOptLcOptMaxPOptLROptOptLROptLR 設(shè)區(qū)間L,R的結(jié)點編號為P，Lc,Rc分別表示P的左右兩個兒子，區(qū)間L,Mid和Mid+1,R。我們可以得到如下轉(zhuǎn)移：算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree 注意到Di

10、st(i,j) = Dist(1,j) Dist(1,i)O(1)算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree 對于邊界情況L,L,MaxL = D(L)MaxR = D(L)Opt = D2(i)表示第i個結(jié)點至子樹內(nèi)某個黑色結(jié)點的路徑中長度的次大值。MaxD(L)+D2(L),D(L) 黑色D(L)+D2(L) 白色問題只剩下如何維護(hù)問題只剩下如何維護(hù)D D和和D2D2的值的值 算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree 該點的兒子到某個黑點路徑的最大長度鏈的頭結(jié)點鏈的頭結(jié)點到某個黑點路徑的最大長度這正是我們前面已經(jīng)維護(hù)了的量這正是我們

11、前面已經(jīng)維護(hù)了的量MaxL一個點向下至某個黑色結(jié)點的路徑鏈的頭結(jié)點鏈的頭結(jié)點算法合集之分治算法在樹的路徑問題中的應(yīng)用Query On a Tree 我們可以使用堆來維護(hù)一個點向下至某個黑色結(jié)點的路徑長度集合O(1)算法合集之分治算法在樹的路徑問題中的應(yīng)用時間復(fù)雜度分析時間復(fù)雜度分析詢問操作： 我們使用堆來存貯每條鏈的最優(yōu)結(jié)果 修改操作： 修改一個點最多影響O(logN)條鏈，對于每條鏈我們需要修改堆和線段樹，O(logN)O(1)O(log2N)路徑剖分進(jìn)一步的分析基于鏈的分治AC算法合集之分治算法在樹的路徑問題中的應(yīng)用三、樹的分治算法的進(jìn)一步探討 基于點的分治刪除一個點后樹的個數(shù)太多，加大了

12、設(shè)計高效算法的難度基于邊的分治刪除一條邊后僅有兩兩棵樹 最壞的時間復(fù)雜度限制了該算法的應(yīng)用改進(jìn)!算法合集之分治算法在樹的路徑問題中的應(yīng)用如何改進(jìn)基于邊的分治的時間復(fù)雜度改變選擇邊的方法？X改變樹的結(jié)構(gòu)！無論選擇哪條邊，結(jié)果都是一樣的 算法合集之分治算法在樹的路徑問題中的應(yīng)用如何改進(jìn)基于邊的分治的時間復(fù)雜度 回想上題，題目所關(guān)注的對象是兩個黑點之間的距離，這就提醒我們可以在不影響樹中黑色結(jié)點之間的距離的前提下加入白色結(jié)點算法合集之分治算法在樹的路徑問題中的應(yīng)用如何改進(jìn)基于邊的分治的時間復(fù)雜度 通過對每個結(jié)點到其兒子的路徑中加入了白色結(jié)點，使之成為了類似線段樹線段樹的結(jié)構(gòu)。 葉節(jié)點為N的線段樹共有

13、2N個結(jié)點，所以含有N個結(jié)點的樹轉(zhuǎn)化后所得的新樹最多包含2N個結(jié)點。每個點的度至多為3 算法合集之分治算法在樹的路徑問題中的應(yīng)用如何改進(jìn)基于邊的分治的時間復(fù)雜度定理： 如果一棵包含N個結(jié)點的樹中每個點的度均不大于D，那么存在一條邊，使得分出的兩棵子樹的結(jié)點個數(shù)在N/(D+1),N*D/(D+1)。改進(jìn)后的算法最壞情況下遞歸深度為 O(LogN)算法合集之分治算法在樹的路徑問題中的應(yīng)用使用基于邊的分治解決上題使用基于邊的分治解決上題一條路徑：1.過中心邊2.在一顆子樹內(nèi)1.過中心邊過中心邊遞歸處理算法合集之分治算法在樹的路徑問題中的應(yīng)用使用基于邊的分治解決上題使用基于邊的分治解決上題 記錄兩個根結(jié)點到其子樹內(nèi)某個黑色結(jié)點的路徑的最大長度 最優(yōu)路徑最優(yōu)路徑修改修改O(logN)詢問詢問O(1)算法合集之分治算法在樹的路徑問題中的應(yīng)用時間復(fù)雜度分析時間復(fù)雜度分析詢問操作： 對每顆樹都記錄其兩個子樹的最優(yōu)值修改操作： 一個點最多屬于O(logN)棵樹，對于每棵樹我們需要修改堆，O(logN)O(1)O(log2N)我們達(dá)到了與使用路徑剖分同階的時間復(fù)雜度。算法更加簡單算法合集之分治算法在樹的路徑問題中的應(yīng)用總結(jié)總結(jié)1.算法的常數(shù)：