2012年3月21日 星期三

PKU1330-Nearest Common Ancestors

題目:http://poj.org/problem?id=1330
(其實就是Lowest Common Ancestor,LCA問題)
給一棵具有N(10000)個節點的有根樹,以及一筆詢問p,q
問點p和點q最近公共祖先的點編號是什麼?


程式碼:http://codepad.org/HgaMlA8m
測資弱了點,只有單筆詢問、但仍不失是經典問題

我覺得這兒已經寫得很完備,請自行參考:
LCA RMQ求解最小公共祖先问题

沒有留言:

張貼留言