山东第一试解题报告

1、解题本题是一个森林的动态连通性问题，采用并查集或者每次询问直接遍历一遍整个图的做法之间复杂度为 O(nm)，实现得好有可能在本题时限 4s 内通过一半左右的数据。一种比较好的解法是采用一种叫作动态树(Dynamic Tree)的数据结构来节点间的连通情况。整个森林中各个动态树支持以下 5 种操作： Make_Tree()，建立一棵只含有一个节点的树 Evert(v)，使节点 v 成为所在树的有根树表示中的树根Link(u,v)，在节点 u 和节点 v 之间加入一条边，使这两个点所在的树相互连通。该操两节点在操作前不连通。定Cut(u,v)，删除边(u,v)。该操定边(u,v)存在Find_Ro

2、ot(v)，返回节点 v 所在树的有根树表示中的树根动态树的后四个操作中都要调用的一个操作是 Acs(v)，通过“”节点 v 的方式，将 v 所在的有根树中从树根到节点 v 的路径剖分出来并单独。相邻（也就是在树中被某条边连结）的路径通过指针 path_parent 连接。由于本问题中初始时刻没有任何边存在，而每次添加、删除边操作都必须剖分。相应节点，因而动态树能保证所有的树都被一些路径完全比如某时刻动态树所的某棵树的路径剖分以及一个节点后的路径剖分如下图所示（粗线表示剖分的路径）：图 1由于每条路径具有线性次序关系，又需要频繁进行路径间的合并、分离、翻转操作，故每条路径均采用伸展树(Spla

3、y Tree)实现，伸展树点的大小为其在树中的深度。具体实现的时候，不必显式每个节点的深度，只要保证每棵伸展树的中序遍历结果与路径相同即可。如图 1 左边的采用伸展树路径后的示意图如下：图 2Acs(v)操作要将节点 v 到根节点的路径出来，过程分为两步首先，将 v 在其所在伸展树中移动到根节点，并将它与其右于节点 v 下方的节点）分离，并设置其已经被独立出来的右点 v（也就是在原先的路径中位的 path_parent 指针指向节然后，利用 v 所在伸展树的 path_parent 指针，不断将 v 所在伸展树与 path_parent 所指向的伸展树合并，直到 path_parent 指针悬

4、空为止如此便将从根节点到节点 v 的路径剖分出来单独了Find_Root(v)操作较为简单，节点 v 之后，找到 v 所在的伸展树中的最小节点，此即为 v所在有根树中的深度最小的祖先，也就是树根Evert(v)操作相当于将从树根到节点 v 的路径上的所有边都反向。的伸展树顺序翻转即可。节点 v 之后，将 v 所在Link(u,v)操作需要在两个节点间连接一条边，由于采用有根树表示，必须先保证其中一个是某棵树的根节点。此处先将 u 置为所在树中的根节点，再将该节点在其伸展树中移动到根节点位置。由于 u 已经是深度最小的节点，因而它在伸展树中的节点为空。再将节点 v移动到伸展树的根节点处，然后将

5、v 设置为 u 的操作。节点，即完成将 u 设为 v 的一棵的Cut(u,v)操作时，首先将 u 置为有根树的根节点，从而使 v 一定是 u 的子节点。节点 v，此时伸展树中 v 的树就是路径中 v 的祖先部分。将 v 与其树分离，就实现了有根树中删除边(u,v)，将一棵树变为两棵树的操作。以上所有操作均基于伸展树的基本操作，比如合并、分离、移动某个节点到树根位置，这些操作都是均摊时间复杂度 O(logn)的。可以证明 Ac s(v)操作对路径的改动是每次操作均摊 O(1)次，而其他各操作只需要调用常数次的 Ac s()以及常数次的伸展树基本操作，因此以上每个操作的均摊时间复杂度为 O(logn)有了动态树数据结构，本题中的 Connect 和 Destroy 均可以用对应的 Cut 和 Link 操作实现， Query 操作只需要比较两个节点所在有根树的根节点是否相同即可。总共的时间复杂度为 O(m logn)，可以在 1s 内通过本题的所有数据。参考文献：1D. D. Sleator, R. E. Tarjan, A Data Structure for Dynamic Trees, JournalScien., Vol.26, No.3, June 1983, 362-391.puter and Syst