dataCLJ遗产动态树研究

动态树研究,HFLS-WJMZBMR,动态树作为传统数据结构，已经经常在比赛中出现了。,现在动态树的难度又得到了前所未有的加强！研究数据结构问题，不但具有理论意义，而且可以极大的加强自己组织和实现代码的能力，很多人的代码能力就是码数据结构练出来的。,传统的动态树问题,为了方便只考虑点权。支持链操作：将一个链上的加一个数/全部改成一个数/支持链询问：询问一条链上的最大值/最小值/权值和支持删除一条边的操作，支持添加一条边的操作。当然要保证还是一个森林。支持换根。,如何解决传统的动态树问题,经典算法LCT。基于核心操作expose()，实现并不困难，但是需要注意细节问题。最近的OI比赛中也经常考到，掌握的话也是不错的。简单的讲一下实现。,支持子树操作的动态树问题,为了方便只考虑点权。支持链操作：将一个链上的加一个数/全部改成一个数/支持链询问：询问一条链上的最大值/最小值/权值和支持子树修改：将一个子数上的加一个数/全部改成一个数/支持子树询问：询问一个子树的最大值/最小值/权值和支持删除一条边的操作，支持添加一条边的操作。当然要保证还是一个森林。支持换根。,如何解决支持子树操作的动态树问题,使用基于LCT实现的TopTree。对expose操作进行各种各样的修改得到新的expose操作。考虑对于子树操作的支持。详细的讲一下实现。,支持链翻转操作的动态树问题,为了方便只考虑点权。支持链操作：将一个链上的加一个数/全部改成一个数/支持链询问：询问一条链上的最大值/最小值/权值和支持删除一条边的操作，支持添加一条边的操作。当然要保证还是一个森林。支持换根。支持链翻转操作，将一条链上的数字整个翻转过来，形态保持不变。,如何解决支持链翻转操作的动态树问题,我们要使用对每个链使用两个splay，一个是通常的splay，维护位置关系，一个是权值splay专门维护权值关系。一个splay的根结点存有到对应splay根节点的对应。同时两个splay按照顺序一一对应。注意到对于一个位置splay中的点，要得出权值splay中的对应点的话，需要先找到根，然后在找到权值splay的对应位置。Expose操作中我们同样可以处理并维护位置splay和权值splay的对应关系。,支持链翻转操作和子树操作的动态树问题,为了方便只考虑点权。支持链操作：将一个链上的加一个数/全部改成一个数/支持链询问：询问一条链上的最大值/最小值/权值和支持子树修改：将一个子数上的加一个数/全部改成一个数/支持子树询问：询问一个子树的最大值/最小值/权值和支持删除一条边的操作，支持添加一条边的操作。当然要保证还是一个森林。支持换根。支持链翻转操作，将一条链上的数字整个翻转过来，形态保持不变。？可以做吗？,一些例题,BZOJ3153Sone1BZOJ3083遥远的国度BZOJ3159决战TsinsenA1354Lord,可持久化动态树,注意到在Top-Tree的实现中，我们现在的整个结构，实际上形成了一个大的树。我们修改一路往上进行，只要对所有的这些节点进行备份，理论上可以实现可持久化！但是我们需要注意到的是，由于这是一个均摊数据结构，我们不能保证每