每年农历九月初九,是中国传统节日“重阳节”。二九相重,称为“重九”,民间在该日有登高的风俗,所以重阳节又称“登高节”。On the ninth day of the ninth lunar month, comes the traditional Chinese holiday: the Double Ninth…
LCA
LCA,即最近公共祖先。
我们用 f ( i , j ) f(i,j) f(i,j) 表示 i i i 的第 2 j 2^j 2j 级父亲,由于 i i i 的第 2 j 2^j 2j 级父亲可以由它的第 2 j − 1 2^{j-1} 2j−1 父亲向上再跳 2 j − 1 2^{j-1} 2j−1 层得到,那么 i i …