LCA,RMQ-ST算法

dfs根据将路径经过的点存下来,那么树就变成线性的,对于任意两个点的lca就是这两个点在数组中第一次出现的位置构成的区间中dep最小点。用rmq维护这个最小值。

 

LEAVE A COMMENT