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 ( 推薦閱讀指數 : 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 ( 推薦閱讀指數 : 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(lo{g}^{2}n)$

---

我們有

$lo{g}^2$
是因為我們二分搜深度
再用

$log$個數字湊出一個深度
這兩件事，某種意義上可以合併(?

---

假設最終要跳到的點

$x$
跟現在深度相差

$d$
二進位表示是

$10110$

---

$10110$

先看看最高位

$10000$ : 非CA(因此會跳)

再看看次高位

$11000$ : 是CA(因此不跳)
.
.
.

---

最後會跳到哪 ?

---

root
CA
CA
CA
LCA
A

$$a
A

$$ a
N

$$ N
N

$$ N

---

root
CA
CA
CA
LCA
A

$$N
A

$$ N
A

$$ N
A

$$ N

---

所以需要特判!!

---

零碎

---

把根的父親設為自己

---

二分搜上限直接設

$\lceil log(N)\rceil$

---

延伸閱讀

---

用樹上歐拉路徑做LCA(made by 塗大為)
Sparse table(made by 吳聖福)
( 推薦閱讀指數 : 4/5 )