_Youngxy

了解到一个quan新的东西： 用ST表（欧拉序）实现LCA(树上最近公共祖先) 欧拉序 前序遍历得到的序列，叫dfs序但数字可以重复出现，一进一出，叫欧拉序会发现根结点总在中间而根结点是该段序列深度最小的点因此两个点的LCA，就是在该序列上两个点第一次出现的区间内深度最小的那个点 即转化为区间RMQ问题，可以用ST表当然你可以再写一棵线段树（如果有修改操作）…