欧拉环游序求Lca

Pre 欧拉环游序

在对一棵树进行dfs时，每次进入一个节点，或者从某个节点的子节点回溯时，将此节点的编号加入一个序列，最后得到的这个序列就是欧拉环游序。

1.先dfs求出欧拉环游序Oula[]

2.记录每个节点x第一次出现在欧拉环游序中的位置为h[x]

3.x,y的Lca就是Oula[h[x]~h[y]]中深度最小的节点

PS：可以用ST表预处理最小值，O(1)回答询问

Time：欧拉环游序求Lca（ST表预处理）的时间复杂度是O(nLogn)+O(1)*q的，q是询问次数

Memory：储存欧拉环游序的数组Oula要~~尽量向大开~~开到边的数量*2，避免RE

所以欧拉环游序求Lca一般用来处理n不是很大，而询问很多的情况

~~这个算法既然有人用肯定就是正确的啊~~qwq~逃

仔细思考一下，x,y第一次出现的位置中间都是些什么什么节点

不难想出，一定都是x,y的Lca的子树上的节点，因为深度小于Lca的点都会在遍历Lca的子树后才会加入欧拉环游序，而且如果从x要走到y肯定要经过Lca

所以正确性显然

给大家一道水题例题练练手

代码在这里↙不懂的可以点进去看一下