树的其他知识——欧拉序列

walk_alone · 2021-02-13 19:58:50 · 个人记录

（本文尚在更新中）

最近看刘汝佳的书，无意间看到了一个东西：欧拉序列，感觉非常有用。

欧拉序列的构造方法如下：

对于有 n 个节点一棵树，用 dfs 访问它的时候，无论是遍历还是回溯（注意不是到一次记一次）都把节点记录下来，这样构成了一个长度为 2n-1 的序列就是欧拉序列。

例如，对于下面这样一棵树，构造它的欧拉序列的方法如下：

首先先进行正常的 dfs。按照 dfs 的顺序，我们会走到 1，这个时候把 1 加到整个序列中。然后是 2，接着是 5。这个时候我们要返回了，可以再把 5 加进去，也可以不加。因而在第一条链走完的时候，我们有 1,2,5。

接下来，我们返回到了 2。可是 2 的子树没有遍历完——还有 6，因而我们下去走 6，加入 6。等我们再回溯到 2的时候，2 的子树终于走完了，我们要将 2 加进去，再接着回溯。因而我们的欧拉序列变成了 1,2,5,6,2。

接着走 3，下去走 7，回来的时候补上回溯的 3。整个序列变成 1,2,5,6,2,3,7,3。

最后就是 4 这颗子树了。按照同样的方法，我们可以得到这部分的欧拉序列为 4,8,9,10,9,4。最后回到 1 的时候，补上回溯的 1，整个流程结束。

因而它的欧拉序列就是这样：1,2,5,6,2,3,7,3,4,8,9,10,9,4,1。

那么，我们搞出这样一个序列，有什么用呢？

用处大的很！

首先，一个节点 u 的子树，在欧拉序列中，它的子树一定是夹在这个节点第一次出现和最后一次出现的中间。例如，还是用上面的这棵树。对于 4 的子树—— 8,9,10，都是出现在两次 4 中间。2 的子树也是夹在两次 2 的中间。

其原因在于：第一次出现代表了向下遍历这个节点。在子树中可能多次回溯访问到这个节点，但是当子树没有走完的时候不会往上，而是继续往下，去遍历它的其他儿子；等到全部走完，它最后一次出现，此时就会继续回溯，这个子树就被遍历完成了。这个时候在欧拉序列中一个节点的子树就会是连续的一段。

因而对于一个非叶节点，可能会遍历出现多次。我们用pos数组存储第一次到这个节点的编号（就是上面的数组下标）。其代码实现也非常简单：

void dfs(int place,int father)
{
    st[place] = ++ind;//子树区间起始，为自身
    euler.push_back(place);//vector<int>euler 表示了整个欧拉序列
    for (int i = headers[place]; i;i=que[i].next)
        if(que[i].to!=father)
            dfs(que[i].to, place);
    if(euler.back()!=place)//回溯过程。如果最后一个是自己，证明是叶节点，不用重复加入；反之则需要加入自己以终止这个子树
    {
        ed[place] = ++ind;
        euler.push_back(place);
    }
    return;
}

同时，我们可以记录每个节点的深度depth。还是用刚刚的那棵树，我们把欧拉序列中节点对应的depth也标进来：

（挖坑）

欧拉序列有两个应用：LCA问题和树的动态查询。

LCA问题

先考虑一般的情况：u,v不存在直接的祖先关系，即，存在一个节点w，满足u,v分属w的两个儿子的子树内。显然，由刚刚的分析，u,v一定出现在w的子树范围内；但是w的祖先同样满足这个关系。我们这时就要找到w特殊的地方，w的祖先不具有的特性：在u,v第一次出现的时候，w的祖先并不会出现，只有w会出现！

因为w的子树的欧拉序列是连续的，当w子树不走完的时候，不会回溯去w的祖先，而是继续在w的其他儿子中遍历。当第一次访问到u的时候，w和祖先都在前头；从u回溯上去，w没有出现；找到了w，由于v所在的子树尚未遍历，不会急于回溯，而是下去遍历v所在的子树；找到第一次v之后，后面再会出现回溯的w和它的祖先，但是这已经不是我们关心的序列了。所以整个序列长这个样：

也就是说：在u,v第一次出现的范围内，w是唯一能访问到的深度最小的节点。结合下面的图表理解：

（挖坑）

对于u是v祖先的情况，情况照旧：因为序列大体呈现\cdots,[u,\cdots ,v],\cdots, u，因而答案还是u。

于是，找LCA就变成了在线段树中找区间最小值的问题了，维护的正是depth数组。该方法预处理时间复杂度O(n)，单次查询和线段树一样O(logn)，总复杂度和倍增的复杂度相同。

树的动态查询

（挖坑）