SPOJ 10707. Count on a tree II

Brief description:

… 給定一棵樹點權樹,求樹上兩點之間的路徑上,出現過多少種不同的權值。

Tags: 樹上莫隊演算法、主席演算法

Analysis:

… 主席演算法太意識流了。。無限仰慕。。。 /$:Orz 。

先寫莫隊演算法吧。。準備工作,開 A、B、C 三個數組。。。
。。A 數組離散掉點權,B 數組展開 dfs 序列,C 數組統計數字已經出現了多少次。。。
、先一次 dfs() 得到各種序列信息,對於每個點 u,。。。進入的時刻在 B 數組中標記 + A[u],離開的時刻標記 – A[u]。。
。。另外記錄其進入的時刻 st[u]。。(這個量後面求 lca 的時候也要用到 。。。

。。這樣得到了暴力演算法。。。對於詢問 (u, v),只要從 st[lca(u, v)] 時刻開始,分別掃描到 st[u] 和 st[v] 的位置,
注意 lca 的位置只取一次。。

先把至此為止的部分調對。。之後開始調整詢問順序。。。
。。我一開始的策略是根據 lca 進行分組。。。不過這個退化的太厲害了。。
(。。貌似是組與組之間的轉移沒處理好。。不過這樣對於一個詢問。。就有三個指針位置。。莫非要跑三維曼哈頓最小生成樹?。。。

。。然後我就 yy 了一下。。因為 lca 的位置依賴於 u, v。。。Orz。。
。。。這樣就只對後面的兩個軸跑莫隊演算法。。複雜度雖然不太清楚。。不過好像能過的樣子。。。

樹上莫隊演算法。。(30s+ 。。。

External link:

http://www.spoj.pl/problems/COT2/
http://seter.is-programmer.com/posts/32857.html