EulerTourTree 发表于 2019-12-15 分类于 ACM ， 学习笔记 ， 树 阅读次数： 本文字数： 241 阅读时长 ≈ 1 分钟 nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Euler Tour Tree 任何一颗树都能够用欧拉旅行路径来表示，欧拉旅行路径是一个序列，他记录了一颗树的dfs的时候的顺序，记录了进入每个节点的时间和退出该节点的时间，这样以后，子树就成了ETT上连续的区间 ，当我们对子树进行交换的时候，我们就可以将这个区间平移。这里我们用splay维护即可