声明：本篇文章搬运自 CF 上的一篇文章。在搬运时，本人已经取得了原作者的同意。
Upd on 12.31：修正了一处错误和一处表意不清。
引入
在许多问题中会给定一棵树的所有边，要求指定一个节点为根并且得知每个节点的父节点。此时通常会使用 DFS 进行计算。但我们希望其可以更快以抢到某题的最优解或冲过毒瘤题。
算法设计
由于不管使用何种数据结构存边都会导致较大的常数，我们考虑不再存储每一条边，而是存储每个节点 i 的度数 deg_i 以及相邻节点的编号异或和 xor_i。事实上，这些信息足够让我们还原整棵树。考虑从小到大枚举每个点 i，并令 p=i。执行以下步骤：
- 若 deg_p=1，则说明 p 此时只与一个节点有边。此时 xor_p 即代表这个节点的编号。将 xor_p 视作 p 的父亲，并令 xor_{xor_p}\gets xor_{xor_p}\oplus p,deg_{xor_p}\gets deg_{xor_p}-1。这个操作相当于将 p 从树中删去并维护受影响的节点的信息。再令 deg_p=0 以防止 p 再次被访问。在此之后，因为 xor_p 也可能变为叶节点，故令 p\gets xor_p，回到该步骤的开始。
- 若 deg_p 不为 1，则说明此时与 p 相连的节点不止一个，则无法简单的处理该节点，跳过。
不难发现在做完上述操作后所有的 deg_p=0，则整棵树被删空。此时存储的 xor 数组为整棵树以某个点为根时的每个父亲结点。
事实上，这个根节点是可以被指定的。只需要将它的 deg 设为 0 即可保证其不会被访问。不难发现算法结束后除了它之外的所有节点的 deg 为 0，则我们得到了以该节点为根时所有节点的父亲。由于该算法仅涉及到了加减法以及异或操作，故常数较小。
如何得到 dfs 序
注意，此处的算法与文章中提到的不同。
我们设 dfn_p 表示该点在 dfs 序中的排名， siz_p 表示子树大小，dif_p 表示 p 与其父亲 dfn 的差值（即在遍历完 p 的父亲后再遍历包括点 p 在内的多少个点可以到达点 p）。特别地，对于根节点 r，有 dif_r=1。则在上述算法删去点 p 前额外按顺序做以下操作：
- 令 siz_p 加一，因为自己尚未被统计。
- 此时 siz_{xor_p} 为在点 p 之前被遍历到的兄弟节点的子树大小之和。我们希望 p 在遍历完这些节点的子树后再被遍历。故令 dif_p\gets siz_{xor_p}+1。
- 令 siz_{xor_p}\gets siz_{xor_p}+siz_p。
对于任意点 p，其所有祖先的 dif 之和即为其 dfn。若按上述遍历顺序的倒序遍历所有节点，则每个节点的父亲都会先于该节点被遍历到，则 dfn 不难计算。
注意，该算法不仅可以应用在此处，如果输入中直接给出了每个节点的父亲也可以使用此算法。
对边的处理
在某些问题上，我们不仅希望得到每个节点的父亲，还希望得到其连向父亲的边。类比上述的处理方式，可以设一个变量表示与某个点相邻的所有边的编号异或和，用与上面类似的方式维护即可。如果边上的信息是一个整数，则同样可以记录边权的异或和。
在 [NOI2011] 道路修建 中，本算法在除了使用快读快写外没有刻意卡常的情况下，目前（2024.12.27）为最优解，且运行时间是第二名的一半。