SPOJ 2666. Query on a tree IV

Brief description:

。帶邊權版本的捉迷藏。。

Analysis:

先引用論文。。

路徑剖分與樹的分治的聯繫:

由於路徑剖分與樹的分治均可以解決樹中路徑的問題,我們不禁疑問,它們是否有著千絲萬縷的聯繫呢?答案是肯定的。我們首先畫出一棵樹及其剖分 (如圖(a)),我們似乎看不出有什麼特殊,我們不妨把它的樣子稍加改變 (如圖(b)),按照點到根結點路徑上的輕邊個數分層擺放。

這時我們就能明顯的看出路徑剖分與樹的分治兩種演算法其實有著驚人的相似,我們上一節中介紹了分治的兩種方式:刪除一個點,或一條邊,而路徑剖分相當於每次刪除了一條鏈!所以路徑剖分演算法可以看做是基於鏈的分治,而且這種分治還有一個特點,每次被刪除結點的兒子必將作為下一次刪除的鏈的頭結點。這樣,就給我們的維護帶來了方便。而正如我們第一節中講的,每個點到根結點路徑上的輕邊個數是O(log N) 的,這樣演算法的時間複雜度便有了保證。

—————— 摘自 NOI 09 冬令營論文 《分治演算法在樹的路徑問題中的應用》by qzc

上面這段話揭示了樹鏈剖分的更深一層的含義,由此我們只要專註考察最高點經過一條重鏈這個子問題。
方法是線段樹,左右各建立一組輔助信息,然後模仿 GSS 中的方法維護就可以了。

但是對於葉子的地方還要仔細處理,需要對每個結點建立一個大根堆,維護自此結點以下最遠黑點距離。。
而維護這個堆。。又可以用更下層結點的線段樹信息。。。(因為 「每次被刪除結點的兒子必將作為下一次刪除的鏈的頭結點」。。

最後對所有的線段樹,再建一個全局堆維護最終詢問。。。
(。。總之這裡的堆要涉及到複雜的修改操作,另外還需要支持詢問次小值,必須手寫。。。
修改的時候沿著跳鏈的方向,對堆和線段樹交替維護即可。。複雜度 O(log^2n)。。。

樹鏈剖分(4.7s +- 。。。
邊分治(14.7s ++。。 。且存在一定幾率會 T 。。反覆提交可破。。。

(邊分治的話不需要維護線段樹,思考起來也更直接。。維護的時候直接記錄每個點在哪些子樹里,直接掃一遍過去就行了。。
(不過代碼可變的地方也要多些,而且看起來的表現給人感覺不太穩定的樣子。。。
(PS:.這樣一來 QTREE 系列也就 ALL CLEAR 了。。。不過.。。好像這題現在已經成為路人題了吧?。。。

External link:

http://www.spoj.pl/problems/QTREE4/