RMQ:区间最大最小值
LCA：最近公共祖先
若有一棵二叉树：
1
/ \
2 3
/ \ \
4 5 6
构造一个深搜序列：
1 2 4 2 5 2 1 3 6 3 1（从根节点出发，先序遍历所有点，再回到根）
然后记录每个节点在上面那个序列里第一次出现的位置
1 2 3 4 5 6
pos： 1 2 8 3 5 9
接下来用ST算法构造深搜序列的RMQ
于是可以直接转化：
LCA(4,5)=RMQ(pos(4),pos(5))
当然很多情况下这样做不如直接用tarjan
啊写完了好开心 去做题
度娘不要吞