TOJ310 尋找問題

印象中是高一寒訓學長出的題目，結果到現在才會寫哈哈

連結：TOJ310 尋找問題

題目：

給定一棵樹，Q次詢問，每次詢問從a到b的路徑中的中點編號

若沒有中點請找最靠近中間的兩個點，由小到大輸出

做法：

有一個的經典題目是這樣的：給定一棵樹，求任兩點 a到b的距離

我們可以求出a, b的LCA，答案即是D[a]-D[lca]+D[b]-D[lca]，其中D為深度

而這題可以直接利用這個方法，求出距離後在由比較深的點往上爬(距離/2)的高度

這裡用倍增法求LCA，後面爬樹時也可以利用

code: