首页 > 笔记 > 奇怪的思想——Euler Tour

奇怪的思想——Euler Tour

引子

颓废的时候想到了这个思想,好像比较有趣。

Euler Tour

何为Euler Tour?

这是一种树的展开方式。和普通的dfs序不同的是,每个节点都会出现几次,也就是递归开始的时候和结束的时候都会记下。就是每次递归到这个点都记下。空间复杂度不佳。

这也是非常好想的,实现也很简单。

这个的应用有什么呢?LCA!

对于每个点记录它在Euler Tour上第一次出现的位置$first[i]$。对于Euler Tour上每个点记录一下它的深度$depth[i]$。

然后查询两点的lca就是$first[i]-first[j]$之间的$depth$最小值对应的点就是两点的lca。

这个可以用rmq实现$O(1)$。。

(好像太基础了

下面是重头戏。

我们找一棵大点的树。

我们能发现一个性质,一个点的第一次出现和最后一次出现之间就是它的子树。

这让人感觉非常愉悦,对于动态树问题,我们发现它的子树问题比较难处理。所以我们可以看看它资瓷不资瓷动态树别的操作。

先看看$link$

这很资瓷啊,在最后加个点就可以了。

$cut$

就是$link$反过来。。

还有一个就是换根操作。。

假如我们要把4号换成根。

于是我们可以用一种数据结构来维护Euler Tour,比如Splay或fhq Treap,然后就能做一类动态树问题。

听起来不错啊,代码量也不错啊,那就来愉快的实现一下吧。

但是好像有些不对啊,对于换根操作,会把序列直接打乱啊,根本无法维护一个点出现的第一个和最后一个点。

真是令人愉快啊~~~


1 COMMENT

  1. cyf2017-06-29 下午7:30

    太神了

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×