poj 1330 Nearest Common Ancestors (lca,用dfs+rmq在线求解)

2016年5月19日 0 作者 CrazyKK

poj1330题目链接

题意:给出一棵树,求两点的lca.
思路:将lca转化成rmq在线求解。

代码部分参考了:参考代码

感觉实现得很巧妙。。。
把树存成了有向图,dfs遇到的时候一定是第一次遇到,此时更新R.
然后第二次遇到某个点就是在回溯的时候了。

算法学习链接