如何理解基于Euler tour labelling的图root函数算法？

前置基础 #

你提到的Euler tour labelling（欧拉环游标签）本质就是对树做深度优先遍历时，给每个节点记录两个时间：第一次访问到该节点的入时间，和遍历完该节点所有子节点后的出时间，每条父子边的标签就等于子节点的入时间。

符号定义通俗解释 #

• L(v)：现有标签规则下，节点v对应的[入时间, 出时间]区间
• L(e)：现有标签规则下，边e对应的标签值
• written_L：你当前已经在用的旧版欧拉环游标签
• root(L)：旧标签对应的原有根节点
• P_L(u,root(L))：在旧标签对应的树结构里，从你要设置的新根u到旧根的唯一路径
• L⁻¹(x)：给一个标签值x，反向查找它在旧标签里对应的节点或者边
• rev(e)：有向边e的反向边，比如e是a指向b，rev(e)就是b指向a
• sub_L(v)：旧标签里v节点的所有子节点加上v自己组成的子树
• [a,b)：左闭右开的数值区间，包含a但不包含b
• rot(k,x,n)：循环移位函数，把0到n-1这n个数字首尾相连排成环，从k的位置开始数x步，落到的数字就是返回值，比如n=5、k=2、x=3，那么从2开始数3步是2→3→4，返回值就是4
• ⊕：这里就是简单的标签替换或者区间拼接，不用做特殊理解

root(written_L,u)函数执行逻辑（大白话版） #

这个函数的核心逻辑就是把树的根从旧根换成u，相当于把u到旧根的路径方向整个反过来，其他旁支结构不变，对应调整标签即可，步骤如下：

1. 先找到两个基础信息：旧标签对应的原有根节点，还有从新根u到旧根的唯一路径，把这条路径上的边按从u到旧根的顺序记录下来
2. 欧拉环游的标签总长度是固定的，等于节点数的2倍，因为每个节点都会被访问一次、离开一次，总步数不会变
3. 取出u在旧标签里的入时间，记为整体偏移量，后面所有标签的调整都基于这个偏移量，相当于把整个标签序列的起点换到u第一次被访问的位置
4. 按节点所属位置不同，分别调整标签：
   • 既不在u到旧根的路径上，也不是路径上节点挂的旁支子节点：直接把旧标签按偏移量做循环移位即可，相当于整个序列换了开头，内部顺序不变
   • 正好在u到旧根路径上的节点：先把旧的入时间和出时间调换，再做循环移位，因为这条路径原来的方向是从旧根到u，现在反过来变成u到旧根，原来的父节点变成子节点，进出顺序自然也反过来
   • 路径上节点挂的旁支子树（不在主路径上的子节点）：先把整个子树的标签区间做内部翻转，再做循环移位即可
5. 边的标签同步调整：路径上的边直接用原来反向边的标签，其他边的标签对应自己连接的子节点的新入时间修改即可
6. 所有节点、边的标签更新完成后，组合起来就是新的欧拉环游标签

内容的提问来源于stack exchange，提问作者NeverSayEver