###### tags: `HW` --- slideOptions: transition: slide --- # DSA HW2 演習課 --- ## 目錄 1. 輸出入優化 2. 廢話 3. Lowest Common Ancestor 4. 另一種二分搜 5. 零碎 6. 延伸閱讀 --- ## 輸出入優化 ---- ios_base::sync_with_stdio(0); cin.tie(0); [chino](http://chino.taipei/note-2016-0311C-%E7%9A%84%E8%BC%B8%E5%87%BA%E5%85%A5cin-cout%E5%92%8Cscanf-printf%E8%AA%B0%E6%AF%94%E8%BC%83%E5%BF%AB%EF%BC%9F/) ( 推薦閱讀指數 : 2/5 ) ---- ### 結論 如果要用cin/cout， 1. 加上輸出入優化 2. 用'\n' 而非endl 3. 不要使用scanf/printf ---- 如果要用printf/scanf， 1. 不要加上輸出入優化 2. 如果混用cin/cout還是可能變慢 ---- Note : 1. cin/cout加了輸出入優化後，孰優孰劣見仁見智 2. cin/cout較慢，不是因為需要判斷型別。 (型別判斷在編譯時就做了) --- ## 廢話 ---- ### 父節點(父親) 往上走一格 ---- ### 子節點(兒子) 你是你父親的兒子 ---- ### 祖先 自己和往上可以走到的點 (自己和父親和父親的祖先) ---- ### 深度 你跟根的距離 --- ### Lowest Common Ancestor (LCA) Definition : 最低的 共同的 祖先 [DJWS](http://www.csie.ntnu.edu.tw/~u91029/Tree.html#5) ( 推薦閱讀指數 : 3/5 ) ---- 祖先們 : root CA CA CA LCA A $\ ~$a A $\ \ \ ~$ a A $\ \ \ \ \ ~$ a A $\ \ \ \ \ \ \ ~$ a $\ \ ~$ 我 $\ \ \ \ ~$ 不是我 ---- #### Jump Pointer Algorithm 中文俗稱倍增法 中心思想 : 如果$(a,b)$的LCA是在$x$節點，那麼以$x$為分界， 在所有 $a,~b$ 的祖先中，若是$x$的祖先， 必為共同祖先，反之必不為 ---- 所以是否為祖先具有單調性(可二分搜的性質) ---- 但是我要怎麼找到第$k$輩的祖先? ---- 維護所有節點的$2^i$輩祖先 維護方法：已知所有節點的$2^0$輩祖先 而一旦有了$2^i$輩祖先，易知$2^{i+1}$輩祖先 ---- 但是我要怎麼知道第$k$輩的祖先是不是CA? ---- 先把深度深的跳到跟淺的一樣深 $(a,b)$同時跳，看看是否跳到同一個點 ---- 這樣就可以AC了(吧? --- ### 另一種二分搜 ###### (通常都是這樣做) ---- 剛剛那種二分搜的方式是$O(log^2~n)$ ---- 我們有$log^2$ 是因為我們二分搜深度 再用$log$個數字湊出一個深度 <span>這兩件事，某種意義上可以合併(?<!-- .element: class="fragment" data-fragment-index="1" --></span> ---- 假設最終要跳到的點$x$ 跟現在深度相差$d$ 二進位表示是$10110$ ---- $10110$ <span>先看看最高位<!-- .element: class="fragment" data-fragment-index="1" --></span> <span>$10000$ : 非CA(因此會跳)<!-- .element: class="fragment" data-fragment-index="2" --></span> <span>再看看次高位<!-- .element: class="fragment" data-fragment-index="3" --></span> <span>$11000$ : 是CA(因此不跳)<!-- .element: class="fragment" data-fragment-index="4" --></span> <span>.<!-- .element: class="fragment" data-fragment-index="5" --></span> <span>.<!-- .element: class="fragment" data-fragment-index="5" --></span> <span>.<!-- .element: class="fragment" data-fragment-index="5" --></span> ---- 最後會跳到哪 ? ---- root CA CA CA LCA A $\ ~$a <span><!-- .element: class="fragment highlight-red" data-fragment-index="0" -->A</span> $\ \ \ ~$ <span><!-- .element: class="fragment highlight-red" data-fragment-index="0" -->a</span> N $\ \ \ \ \ ~$ N N $\ \ \ \ \ \ \ ~$ N ---- root CA CA CA <span><!-- .element: class="fragment highlight-green" data-fragment-index="0" -->LCA</span> A $\ ~$N A $\ \ \ ~$ N A $\ \ \ \ \ ~$ N <span><!-- .element: class="fragment highlight-green" data-fragment-index="0" -->A</span> $\ \ \ \ \ \ \ ~$ N ---- 所以需要特判!! --- ### 零碎 ---- 把根的父親設為自己 ---- 二分搜上限直接設$\lceil log(N) \rceil$ --- ### 延伸閱讀 ---- [用樹上歐拉路徑做LCA](https://tioj.ck.tp.edu.tw/uploads/attachment/11/54/7.pdf?fbclid=IwAR17Z3VOAf9nXygghEkx8kYw_tKBsQk3YNe2FvPNM9AyRjXDIYOlQzNLeWY)(made by 塗大為) [Sparse table](https://tioj.ck.tp.edu.tw/uploads/attachment/5/28/6.pdf)(made by 吳聖福) ( 推薦閱讀指數 : 4/5 )