轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年2月20日 星期四

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的時候進出的順序記錄下來。