DSA HW2 演習課

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較慢，不是因為需要判斷型別。
   (型別判斷在編譯時就做了)

父節點(父親)

往上走一格

子節點(兒子)

你是你父親的兒子

祖先

自己和往上可以走到的點
(自己和父親和父親的祖先)

深度

你跟根的距離

祖先們 :

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\)個數字湊出一個深度
這兩件事，某種意義上可以合併(?

假設最終要跳到的點\(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 )