poj 1986 Distance Queries (lca,在线做法dfs+rmq)

2016年5月20日 0 作者 CrazyKK

题目链接
题意:求树上两点的最短距离?
思路: dis[i]表示点i到根节点的距离,那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)].
只需要求出rmq+dfs的在线方法求出lca(u,v)即可。