樹 建議閱讀順序（有些沒有嚴格的順序關係）： 線段樹 \(\rightarrow\) 輕重鏈剖分（長短鏈剖分） \(\rightarrow\) \(LCA\&LA\) \(\rightarrow\) 全局平衡二叉樹 \(\rightarrow\) 動態樹 數據結構 線段樹 https://www.c ...
樹
建議閱讀順序（有些沒有嚴格的順序關係）：
線段樹 \(\rightarrow\) 輕重鏈剖分（長短鏈剖分） \(\rightarrow\) \(LCA\&LA\) \(\rightarrow\) 全局平衡二叉樹 \(\rightarrow\) 動態樹
數據結構
線段樹
https://www.cnblogs.com/efX-bk/p/segment_tree.html
動態樹
https://www.cnblogs.com/efX-bk/p/basic_dynamic_tree.html
全局平衡二叉樹
需要會樹鏈剖分
先重鏈剖分，重鏈剖分中，跳輕邊的次數為 \(O(\log n)\) 的，然後用一個數據結構（線段樹之類的）維護了重鏈上的信息
但在重鏈上維護信息可以做到更優，考慮把重鏈表示成一顆二叉樹，滿足：
1.這棵樹的中序遍歷是重鏈按深度遍歷的結果，
2.二叉樹上的節點關於輕子樹的大小是最平衡的
第一點容易滿足，第二點可以用更為形象的解釋：把重鏈轉為序列，以每個點輕子樹的大小+1 為加權求加權中點作為根，然後遞歸到左右兩邊
稱二叉樹上的邊為重邊，其餘邊為輕邊
由於是重鏈剖分，跳一次輕邊 \(size_{當前點}\) 至少加倍，至多跳 \(O(\log n)\) 次
由性質2，跳一次重邊 \(size_{\text{輕子樹}}\) 至少加倍，至多跳 \(O(\log n)\) 次
於是一共只會跳 \(O(\log n)\) 次，但比起重鏈剖分的好處是我們用子樹替代了序列，而子樹操作常常容易做到 \(O(1)\)（細節還是很多的，比如要判斷有沒有右子樹什麼的）
上面說的只適用於鏈的操作，如果是子樹操作就需要把所有輕兒子往上放，訪問到時就取出來，子樹操作就對於所有輕兒子都打一個標記，重兒子特判一下
Trick
輕重鏈剖分
從某個點出發 dfs 整顆樹，遇到一個新點就給它一個新的編號，這樣一個子樹就是連續的一段編號，這種方式被稱為 \(dfs\) 序
\(dfs\) 序雖然解決了子樹問題，但不能解決鏈上的問題，考慮把一條鏈拆成若幹段連續的 \(dfs\) 序
\(siz_x\) 表示以 \(x\) 為根的子樹的大小
定義一個點 \(u\) 所有子樹中 \(siz\) 最大的是 \(u\) 的重兒子，記為 \(son_u\)，其他兒子都是輕兒子
這樣，從一個點出發，我們優先遍歷重兒子，這樣顯然不會破壞 \(dfs\) 序的性質
一個點到重兒子的邊記為重邊，其他邊記為輕邊
發現
\[siz_{son}>siz_{\text{輕兒子}} siz_u=siz_{son_u}+\sum siz_{u\text{的輕兒子}} \]轉化一下就是
\[siz_{u\text{的輕兒子}}\le \frac 12siz_u \]所以跳一次輕邊 \(siz\) 至少加倍，且不會超過 \(n\)，於是從任意節點到根節點至多跳 \(O(\log n)\) 次輕邊，而重邊上的 \(dfs\) 序是連續的，於是就可以把任意一段樹鏈分為 \(O(\log n)\) 段連續的 \(dfs\) 序區間了
長短鏈剖分
就是把上面重兒子的定義改為深度最大的兒子
LCA&LA
都很容易做到線上 \(O(\log n)\)
但可以在靜態樹的情形下優化到 \(O(n)\) 預處理，\(O(1)\) 線上詢問
首先介紹歐拉序：
就是遍歷所有節點，掃到一次就往一個序列尾部插入該節點，這個序列就是歐拉序。（很多時候只記錄第一次和最後一次就夠了）
不難說明歐拉序的大小為 \(O(n)\)
在歐拉序上關於深度建立 ST 表就可以做到 \(O(n\log n)-O(1)\) 的複雜度做 LCA
為了避免建表的複雜度，對於序列進行塊長為 \(\frac {\log n}{2}\) 的分塊，對於塊間建立 ST 表，就抵消了建表的 \(\log n\)，變成 \(O(n)\) 了
再考慮散塊，對於歐拉序，相鄰節點的深度差只能為 \(\pm1\)，而我們只關心最大/小值所在的位置，即我們只關註塊內的差分，於是本質不同的塊的種數只有
\[2^{\frac{\log n}{2}}=\sqrt n \]塊內暴力處理所有可能的區間只是 \(O(\log^2 n)\) 的，複雜度為 \(O(\sqrt n\log^2 n)\)，不是瓶頸
然後 LCA 就優化到了理論最優
再來看 LA
朴素的做法是先長鏈剖分，預處理每個點的 \(2^i\) 級祖先
有如下引理
一個點的 \(k\) 級祖先所在的長鏈長度不小於 \(k\)
如果該點和其 \(k\) 級祖先在一條長鏈上，結論顯然成立
如果不在一條長鏈上，顯然可以把該點映射到祖先所在長鏈上深度相同的位置（因為長鏈是最深的，該點不是長鏈，一定不可能更深），然後就轉化為上一種情況了
利用上述引理，對於所有鏈頂，設其對應鏈長為 \(len\)，記錄上下 \(len\) 個點
對於一次詢問，先向上跳 \(2^{highbit(k)}\) 步，設
\[k=k^\prime+2^{highbit(k)} \]則只需再跳 \(k^\prime\) 步，發現
\[k^\prime<\frac k2 \]由引理，此時已經在祖先所在的長鏈上了，按照鏈頂存儲的點就可以 \(O(1)\) 查找了
與 LCA 類似，暴力做法也是 \(O(n\log n)-O(1)\) 的，依然考慮減小樹的規模
可以暴力的把大小恰好不超過 \(\frac {\log n}{4}\) 的子樹從原樹上剪下來，就得到一顆葉子結點數目不超過 \(O(\frac {n}{\log n})\) 的新樹
每個點都可以 \(O(1)\) 對應到葉子上，設詢問節點到任一葉子的距離為 \(d\)，那麼對應葉子的 \(k+d\) 的級祖先就是詢問節點的 \(k\) 級祖先
於是只需要對葉子做暴力的預處理，複雜度 \(O(n)\)
如果詢問的是剪下來的小樹上的節點，依然是一樣的思路：考慮本質不同的大小為 \(\frac {\log n}{4}\) 的有根樹有多少種
然後發現就是括弧序列的種數，於是就是
\[B=\frac {\log n}{4}\\ S=\frac {C_{2B}^B}{B+1} \]\(S\) 就是答案
用 \(dep\) 表示一種樹的最大深度，如果 \(k>dep\) 那就轉換到減去了子樹的新樹上，否則就暴力預處理，複雜度
\[O(SB^2)=O(4^{\frac{\log n}{4}}\log^2n)=O(\sqrt n\log^2n)<O(n) \]然後就可以 \(O(n)-O(1)\) 了
