關于樹上k級祖先

\(\large\texttt{Warning:}\) 此篇部落格其實是對 \(Luogu\ P5903\) 題解區中一些方法的彙總梳理，并不是本人原創！！！

主要思路：通過倍增的思想，存下 \(x\) 的 \(2^i\) 級祖先，在查詢時将 \(k\) 進行二進制分解，分解為 \(\displaystyle\sum^t_{i=1}2^{a_t}\) 次方的形式，再每次向上跳 \(2^{a_t}\) 步，跳完 \(t\) 次後就得到了 \(x\) 的 \(k\) 級祖先。

時間複雜度：\(\cal{O((n+q)\log_2n)}\)

空間複雜度：\(\cal{O(n\log_2n)}\)

主要思路：進行輕重鍊剖分，在查詢時判斷目前點 \(x\) 所在的重鍊頂點是否在其 \(k\) 級祖先上放。若不在其上方，則将 \(x\) 跳至鍊頂的父親節點，并讓 \(k\) 減去這一段的長度，并繼續處理。否則則利用求出的 \(\texttt{dfs}\) 序直接計算。

時間複雜度：\(\cal{O(n-q\log_2n)}\)

空間複雜度：\(\cal{O(n)}\)

主要思路：在輕重鍊剖分法的基礎上，利用倍增預先處理出向上跳 \(2^i\) 次能到達的節點，就可以優化時間複雜度了。

時間複雜度：\(\cal{O(n\log_2\log_2 n - q\log_2\log_2 n)}\)

空間複雜度：\(\cal{O(n\log_2\log_2 n)}\)

咕咕咕