莫隊算法學習筆記（三）——樹上莫隊

樹上莫隊的核心思想，就是将一棵樹轉化成一個序列，然後用普通莫隊來搞。

前言

初始化

以一棵樹為例：

要想對這棵樹進行樹上莫隊，我們第一步就是用一個\(s\)數組把它的括号序存下來：

\(id\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
\(s\)																1​

同時，我們用\(I\)數組存儲每個數字在括号序列中第一次出現的位置，用\(O\)數組存儲每個數字在括号序列中第二次出現的位置。

處理查詢

首先，對于詢問的兩個數\(x,y\)，我們要保證\(I_x\le I_y\)（這可以通過\(swap\)進行保證）。

對于查詢的兩個節點，我們需要對其進行分類讨論。

對于祖先關系的兩個點（以\(1,5\)為例）

我們需要分别找到\(x,y\)在括号序列中第一次出現的位置（即\(1\)和\(9\)）。

然後就能得到一段區間：

\[1,2,4,7,8,8,7,4,5

\]

對于出現兩次的元素，我們将它去掉（在程式中隻要判斷一個元素出現次數的奇偶性即可）。

然後就得到這樣一個區間：

\[1,2,5

而這些恰好就是我們要求解的元素。

簡單說，就是求解區間\([I_x,I_y]\)即可。

對于非祖先關系的兩個點（以\(5,6\)為例）

我們需要找出\(x\)在括号序列中第二次出現的位置和\(y\)在括号序列中第一次出現的位置（即\(10\)和\(13\)）。

然後就能得到這樣一個區間：

\[5,2,3,6

注意，對于出現兩次的元素，我們同樣需要将它去掉，隻不過這個例子中剛好沒有出現這樣的情況而已。

然後我們可以發現，這個區間中的元素就是除\(LCA_{x,y}\)以外要求解的全部元素。

例題

敗得義無反顧，弱得一無是處