动态树的经典应用

——————摘自《高级数据结构》

1。求最近公共祖先
基于动态树的基本操作，我们很容易在较短的时间内求得任意两个结点u和结点v（在同一棵树中）的最近公共祖先。首先对u执行access（u）操作，同时记录被访问过的结点（在平衡树上打标机即可）；然后执行access（v）操作，当第一次碰到已经访问过的点w时，该w就是u和v的最近公共祖先。时间复杂度是O（nlog2n）.
2.并查集操作
在并查集操作一章我们看到了如何维护两个集合进行合并操作，然而并查集不支持既有合并又有分离的操作。类似并查集的树形结构，用动态树来维护这种森林连通性的变换非常方便
3.求最大流
通过用动态树改造最短路径增光路算法，可以再O（nmlog2n）的时间复杂度内得到网络最大流，其中n为顶点数，m为边数。算法的大致思想：刚开始执行时，每个顶点为单独的一棵树，每次增广的时候选择一条未满流的边，用来给当前的树连接新的结点，如果发现已经找到了汇点，那么每次增广的流量就是树中源点到汇点路径上所有边中最小增广量，将路径上的边增广相应流量后，将满流边删去，然后继续执行增广。
4。求最小生成树
增量构造法求最小生成树的方式————依次添加边，如果发现当前的边添加后形成了环，那么将环上的最大边权删去，直到更新完了为止。这种增量式的算法如果用动态树维护将会非常高效。我们所需要的操作除了几个动态树级别的操作之外，还需要维护任意两个点之间的路径上的权值最大的边，该信息可以用平衡树维护。
除了一般的最小生成树之外，其他的一些问题，例如度限制最小生成树或者对边使用有限制的生成树也用动态树问题来建模也可以得到不错的效果。