STEP5::Problem 0134 : 景點問題

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0134
很有趣(?!)的題目。
只要找出LAC就可以了。第一次寫LAC所以寫得很難看。

題目有說兩點只有一條路徑-->這是一棵樹。找出兩點的路徑長就是a點到root+b點到root-2*LAC到root。(好像也可以直接從兩點回朔找LCA---Online LCA Sparse Table，不過我那時候不知道ㄏ.....)
至於怎麼做就是把樹壓扁成陣列，再用線段樹搜區間內深度最小的那點(就LAC啦)。不過因為不用更新，所以可以用Sparsr Table寫，O(n lg n+q)。(下面是用BIT寫的)
(再)至於怎麼壓扁要用時間標記，把DFS的時候進出的順序記錄下來。